hdu3068_최 장 회 문 꼬치마 나 처 (마차 모형)

최 장 답문
Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 20742    Accepted Submission(s): 7522
Problem Description
소문 자 영문 문자 a, b, c... y, z 로 만 구 성 된 문자열 S 를 보 여 줍 니 다. S 에서 가장 긴 답장 문자열 의 길 이 를 구 합 니 다.
답문 은 정반 독 이 모두 같은 문자열 이다. 예 를 들 어 aba, abba 등 이다.
 
Input
120 그룹 을 초과 하지 않 고 여러 그룹의 case 를 입력 하 십시오. 각 그룹 은 소문 자 영문 문자 a, b, c... y, z 로 구 성 된 문자열 S 를 입력 하 십시오.
두 그룹의 case 사 이 를 빈 줄 로 구분 합 니 다. (이 빈 줄 은 처리 할 필요 가 없습니다.)
문자열 길이 len < = 110000
 
Output
각 줄 의 정수 x 는 하나의 케이스 에 대응 하여 이 케이스 의 문자열 에 포 함 된 가장 긴 답장 길 이 를 표시 합 니 다.
 
Sample Input
 
   
aaaa abab
 

Sample Output
 
   
4 3
 

解:马拉车算法模板题,没什么可说的\OvO/ 

#include 
#include 
#include 
#include 
#include 

using namespace std;
const int MANX = 2e5+100;
char str0[MANX],str[MANX<<1];
int p[MANX<<1],len;
void start()//处理原字符串
{
    str[0]='$',str[1]='#';
    len=strlen(str0);
    for(int i=0;ii)p[i]=min(p[2*id-i],mx-i);
        else p[i]=1;
        for(;str[i-p[i]]==str[i+p[i]];p[i]++);
        if(p[i]+i>mx)mx=p[i]+i,id=i;
        if(p[i]>ans)ans=p[i];
    }
    printf("%d
",--ans); } int main() { while(~scanf("%s",str0)) { start(); solve(); } return 0; }

좋은 웹페이지 즐겨찾기