题目大意:

给定两个字符串,在第一个字符串中找到一个最大前缀作为第二个字符串的后缀

 #include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include <climits>
#include <cmath>
#include <cstdlib> using namespace std; #define ll long long
#define N 1000100
char a[N] , b[N];
int _next[N] , extend[N] , len1 , len2; void get_next(char *T){// _next[i]: 以第i位置开始的子串 与 T的公共前缀
int i,length = strlen(T);
_next[] = length;
for(i = ;i<length- && T[i]==T[i+]; i++);
_next[] = i;
int a = ;
for(int k = ; k < length; k++){
int p = a+_next[a]-, L = _next[k-a];
if( (k-)+L >= p ){
int j = (p-k+)>? (p-k+) : ;
while(k+j<length && T[k+j]==T[j]) j++;// 枚举(p+1,length) 与(p-k+1,length) 区间比较
_next[k] = j, a = k;
}
else _next[k] = L;
}
}
void getextend(char *S,char *T){
int maxl=max(len1 , len2);
for(int i= ; i<=maxl ; i++) _next[i]=;
get_next(T);
int Slen = strlen(S), Tlen = strlen(T), a = ;
int MinLen = Slen>Tlen?Tlen:Slen;
while(a<MinLen && S[a]==T[a]) a++;
extend[] = a, a = ;
for(int k = ; k < Slen; k++){
int p = a+extend[a]-, L = _next[k-a];
if( (k-)+L >= p ){
int j = (p-k+)>? (p-k+) : ;
while(k+j<Slen && j<Tlen && S[k+j]==T[j] ) j++;
extend[k] = j;a = k;
}
else extend[k] = L;
}
} int main()
{
#ifndef ONLINE_JUDGE
freopen("a.in" , "r" , stdin);
#endif
while(~scanf("%s%s" , a , b))
{
getextend(b , a);
len1 = strlen(a) , len2 = strlen(b);
int ret = ;
for(int i= ; i<len2 ; i++)
if(extend[i]>ret&&extend[i]+i==len2) ret = extend[i];
if(!ret) puts("");
else{
strncpy(a , b+(len2-ret) , ret);
a[ret] = '\0';
printf("%s %d\n" , a, ret);
}
}
return ;
}
04-25 20:15