Manacher - Girls' research - HDU - 3294

Manacher - Girls’ research - HDU - 3294
제목:
여러 그룹 테스트 용례, 각 그룹 은 문자 c h 와 문자열 s 를 포함 합 니 다.문자열 c h 는 s 의 c h 를 a 로 바 꾸 고 다른 문자 응답 은 같은 '길이' 로 바 꿉 니 다.밤 을 들 어 라: 만약 c h = b 라면 s 중의 b 가 a 로 바 뀌 면 a 는 z 로 바 뀌 고 c 는 b 로 바 뀌 며 d 는 c 로 바 뀌 고...  교 체 된 문자열 s 에 대해 첫 번 째 로 나타 난 최대 답장 문자열 의 시작 과 끝 위 치 를 구하 고 이 답장 문자열 을 출력 합 니 다.하위 문자열 길이 가 2 보다 작 으 면 출력 N o  s o l u t i o n ! 。 여러 그룹 테스트 용례, 각 그룹 에는 문자 ch 와 문자열 s 가 포함 되 어 있 습 니 다. \ \ \문자열 ch 는 s 의 ch 를 a 로 바 꾸 고 다른 문자 가 응답 하 는 것 은 같은 '길이' 로 바 꿉 니 다. \ \ \밤 을 들 어: ch = b 면 s 의 b 가 a 로 바 뀌 면 a 는 z 로 바 뀌 고 c 는 b 로 바 뀌 며 d 는 c 로 바 뀌 고... \ \ \ \ \ \ \ \ \ \ \ \교 체 된 문자열 s 에 대해 서 는 첫 번 째 로 나타 나 는 최대 답장 문자열 의 시작 과 끝 위 치 를 구하 고 이 답장 문자열 을 출력 합 니 다. \ \ \답장 하위 문자열 길이 가 2 보다 작 으 면 No \ solution 을 출력 합 니 다!여러 그룹 테스트 용례, 각 그룹 은 문자 ch 와 문자열 s 를 포함 합 니 다.문자열 ch 는 s 의 ch 를 a 로 바 꾸 고 다른 문자 응답 은 같은 '길이' 로 바 꿉 니 다.밤 을 들 어 라: 만약 ch = b 라면 s 중의 b 가 a 로 바 뀌 면 a 는 z, c 는 b, d 는 c 로 바 뀌 고... 교 체 된 문자열 s 에 대해 첫 번 째 로 나타 난 최대 답장 문자열 의 시작 과 끝 위 치 를 구하 고 이 답장 문자열 을 출력 합 니 다.답장 하위 문자열 길이 가 2 보다 작 으 면 출력 No solution!。

Sample Input
b babad
a abcd

Sample Output
0 2
aza
No solution!

예 를 들 어 1: b - > a, a - z, d - > c 는 새로운 꼬치 a z a z c 를 얻 었 고 첫 번 째 로 나타 난 최대 답장 서브 꼬치 는 a z a 이다.예 를 들 어 1: b - > a, a - > z, d - > c 를 통 해 새로운 azazc 를 얻 었 습 니 다. 첫 번 째 로 나타 난 최대 답장 서브 꼬치 는 aza 입 니 다.예 를 들 어 1: b - > a, a - > z, d - > c 는 새로운 azazc 꼬치 를 얻 었 고 첫 번 째 로 나타 난 가장 큰 회 문 자 꼬치 는 aza 이다.
데이터 범위: 문자열 길이 n < = 200000.T i m e   l i m i t ： 1000 m s ， M e m o r y   l i m i t: 32768 k B 문자열 길이 n < = 20000. \ \Time \ limit: 1000 ms, Memory \ limit: 32768 kB 문자열 길이 n < = 20000.Time limit：1000ms，Memory limit：32768kB
문제 풀이:
먼저 문자열 을 바 꾸 고 말 라 차 를 사용한다.전환: c h 와 a 사이 의 간격 을 보면 다른 문 자 는 모두 이 간격 을 빼 고 뺀 A S C I 코드 가 a 보다 작 으 면 26 을 추가 합 니 다.  말 라 차 의 첫 번 째 최대 회 문 꼬치 가 있 는 중심 위치 i (아래 표 시 는 1 부터), 실제 중심 위 치 는 p o s = * 8970 ° i 2 * 8971 ° 이다.최대 길 이 는 a n s 이 고, 회 문 반경 은 8970 ° (a n s + 1) 2 * 8971 ° 이 며, 시작 위 치 는 p o s - 8970 ° (a n s + 1) 2 * 8971 ° 이 며, 끝 위치: p o s - 8970 ° (a n s + 1) 2 * 8971 ° + a n s - 1.먼저 문자열 을 바 꾸 고 말 라 차 를 이용 하 세 요.전환: ch 와 a 사이 의 간격 을 보고 다른 문 자 는 모두 이 간격 을 빼 고 뺀 ASCII 코드 가 a 보다 작 으 면 26 을 추가 합 니 다. \ \ \ \ \ \ \ \ \마차 의 첫 번 째 최대 리 턴 문자열 이 있 는 중심 위치 i (아래 표 시 는 1 부터) 입 니 다. 실제 중심 위 치 는 pos = \ lfloor \ \ frac {i} {2} \ rfloor 입 니 다. \ \ \ \최대 길 이 는 ans 이 며, 답장 반경 은 \ lfloor \ \ frac {(ans + 1)} {2} \ rfloor 이 며, 시작 위 치 는 pos - \ lfloor \ \ frac {(ans + 1)} {2} \ rfloor, 끝 위치: pos - \ lfloor \ \ frac {(ans + 1)} {2} \ rfloor + ans - 1 입 니 다.먼저 문자열 을 바 꾸 고 말 라 차 를 사용한다.전환: ch 와 a 사이 의 간격 을 보면 다른 문 자 는 모두 이 간격 을 빼 고 뺀 ASCII 코드 가 a 보다 작 으 면 26 을 추가 합 니 다. 말 라 차 의 첫 번 째 최대 회 문 꼬치 가 있 는 중심 위치 i (아래 표 시 는 1 부터), 실제 중심 위 치 는 pos = * 8970 ° 2i * 8971 ° 이다.최대 길 이 는 ans 이 고 회 문 반경 은 8970 ° 2 (ans + 1) * 8971 ° 이 며 시작 위 치 는 pos - * 8970 ° 2 (ans + 1) * 8971 ° 이 며 끝 위치: pos - * 8970 ° 2 (ans + 1) * 8971 ° + ans - 1 입 니 다.
주의:
s t r l e n 함 수 는 순환 에 쓰 지 마 세 요. 상수 가 너무 큽 니 다.strlen 함 수 는 순환 에 쓰 지 마 세 요. 상수 가 너무 큽 니 다.strlen 함 수 는 순환 에 쓰 지 마 세 요. 상수 가 너무 큽 니 다.
코드:

#include 
#include 
#include 
#include 
#include 

using namespace std;

const int N=200010;

char s[N],ch[2];
char Ma[N*2];    //     +    
int Mp[N*2];    //Mp[i]: i          +1

void Manacher(char s[],int len)
{
    int l=0;
    Ma[l++]='$';
    Ma[l++]='#';
    for(int i=0;i<len;i++)
    {
        Ma[l++]=s[i];
        Ma[l++]='#';
    }
    Ma[l]=0;
    int mx=0,id=0;
    for(int i=0;i<l;i++)
    {
        Mp[i]=mx>i?min(Mp[2*id-i],mx-i):1;
        while(Ma[i+Mp[i]]==Ma[i-Mp[i]])Mp[i]++;
        if(i+Mp[i]>mx)
        {
            mx=i+Mp[i];
            id=i;
        }
    }
}

int main()
{
    while(~scanf("%s%s",ch,s))
    {
        int d=*ch-'a';
        int len=strlen(s);
        for(int i=0;i<len;i++)
        {
            if( s[i]-d < 'a') s[i]=char(s[i]-d+26);
            else s[i]=char(s[i]-d);
        }

        Manacher(s,len);
        int ans=0,pos=0;
        for(int i=0;i<2*len+2;i++)
        {
            if(ans<Mp[i]-1)
            {
                ans=Mp[i]-1;
                pos=i/2;
            }
        }

        if(ans>=2)
        {
            printf("%d %d
",pos-(ans+1)/2,pos-(ans+1)/2+ans-1);
            for(int i=pos-(ans+1)/2;i<=pos-(ans+1)/2+ans-1;i++) printf("%c",s[i]);
            puts("");
        }
        else puts("No solution!");
    }
    return 0;
}