2013 ACM/ICPC 长春网络赛E题

时间:2022-01-17 09:24:11

题意:给出一个字符串,要从头、尾和中间找出三个完全相等的子串,这些串覆盖的区间互相不能有重叠部分。头、尾的串即为整个字符串的前缀和后缀。问这个相同的子串的最大长度是多少。

分析:利用KMP算法中的next数组。next数组有一个性质,如果next[b]指向a。a<b。那么 以a作为结尾的原串前缀 是 以b作为结尾的原串前缀 的后缀。

那么如果b是原串的最后一位,那么以b结尾的前缀就是原串,则a结尾的前缀与一个原串的后缀相等。

我们既然找到了一个相等的前缀和后缀,只需要再判断中间是否有相同的子串即可。即判断是否存在next[c]==a,或者next[next[c]]==a,或者……

如果没有我们就缩短前缀的长度,方法就是让a=next[next[b]],a=next[next[next[b]]],这样不断迭代。每次这样判断,直到找到一个中间存在相等串的为止。

#include <cstdio>
#include <cstring>
using namespace std; #define MAX_SONG_LEN 1000005 char song[MAX_SONG_LEN];
int left_link[MAX_SONG_LEN];
int song_len; void input()
{
scanf("%s", (song + ));
song_len = strlen(song + );
song[] = -;
} void kmp(char st[], int next[], int len)
{
next[] = ;
next[] = -;
for (int i = ; i <= len; i++)
{
int temp = next[i - ];
while (temp >= && st[i] != st[temp + ])
temp = next[temp];
next[i] = temp + ;
}
} bool reach(int l, int r)
{
while (r > l)
r = left_link[r];
return r == l;
} int work()
{
int prefix_end = song_len;
while (prefix_end > )
{
if (prefix_end > song_len / )
{
prefix_end = left_link[prefix_end];
continue;
}
int theme_len = prefix_end;
int suffix_begin = song_len - theme_len + ;
int mid_end = prefix_end;
for (int i = prefix_end + ; i < suffix_begin; i++)
if (reach(prefix_end, i) && i - prefix_end >= theme_len)
return theme_len;
prefix_end = left_link[prefix_end];
}
return ;
} int main()
{
int case_num;
scanf("%d", &case_num);
while (case_num--)
{
input();
kmp(song, left_link, song_len);
printf("%d\n", work());
}
return ;
}