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

分析：利用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 
      
       #include 
       
        using namespace std;#define MAX_SONG_LEN 1000005char song[MAX_SONG_LEN];int left_link[MAX_SONG_LEN];int song_len;void input(){    scanf("%s", (song + 1));    song_len = strlen(song + 1);    song[0] = -1;}void kmp(char st[], int next[], int len){    next[1] = 0;    next[0] = -1;    for (int i = 2; i <= len; i++)    {        int temp = next[i - 1];        while (temp >= 0 && st[i] != st[temp + 1])            temp = next[temp];        next[i] = temp + 1;    }}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 > 0)    {        if (prefix_end > song_len / 2)        {            prefix_end = left_link[prefix_end];            continue;        }        int theme_len = prefix_end;        int suffix_begin = song_len - theme_len + 1;        int mid_end = prefix_end;        for (int i = prefix_end + 1; i < suffix_begin; i++)            if (reach(prefix_end, i) && i - prefix_end >= theme_len)                return theme_len;        prefix_end = left_link[prefix_end];    }    return 0;}int main(){    int case_num;    scanf("%d", &case_num);    while (case_num--)    {        input();        kmp(song, left_link, song_len);        printf("%d\n", work());    }    return 0;}