[PKU2752]Seek the Name, Seek the Fame

求所有满足既是S前缀又是S后缀的子串的可能长度。

实际上KMP预处理的时候就是算s[1..j]==s[i-j+1..i]的最小长度，那么当i=len的时候求的p[len]就是既是S前缀又是S后缀的子串的最大长度，因此i=p[i]递归输出p[i]。 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

#include <cstdio>
#include <cstring>

const int MAXLEN(400001);
int len, count, p[MAXLEN], ans[MAXLEN];
char s[MAXLEN];
int main()
{
  while (scanf("%s", s) != EOF)
  {
    p[0] = -1;
    len = strlen(s);
    for (int i = 1, j = -1; i < len; ++i)
    {
      for (; j > -1 && s[i] != s[j+1]; j = p[j]);
      if (s[i] == s[j+1]) ++j;
      p[i] = j;
    }
    ans[count = 0] = len;
    for (int i = len-1; p[i] > -1; i = p[i])
      ans[++count] = p[i]+1;
    for (int i = count; i >= 0; --i)
      printf("%d ", ans[i]);
    printf("n");
  }
}

Comments