信息学奥赛一本通T1458-Seek the Name, Seek the Fame（KMP）

解题思路:

stack<int> st;

* 声明一个栈 `st`，用于存储字符串 `s` 的可行长度。

* **main 函数：**

    * 进入一个循环，不断读取字符串 `s`，直到遇到文件结束符 (EOF) 为止。

    * 对于每个输入的字符串 `s`，执行以下操作：

        * 初始化 `ne` 数组的前两个元素为 0。

        * 计算字符串 `s` 的长度 `len`。

        * 重新计算 `ne` 数组，使用 KMP 算法。

        * 将 `len` 压入栈 `st`，因为 `len` 是必然可行的长度。

        * 循环计算 `ne[len]`，并将 `ne[len]` 压入栈 `st`，直到 `ne[len]` 为 0。

        * 输出栈 `st` 中的所有元素，这些元素表示字符串 `s` 的所有可行长度。

**KMP 算法（重新计算 ne 数组）：**

```cpp

//计算字符串s的next数组,模板背！

ne[0] = ne[1] = 0;

int len = strlen(s+1);

for(int i = 1,j = 0;i < len;i++)

{

while(j && s[i+1] != s[j+1]) j = ne[j];

if(s[i+1] == s[j+1]) j++;

ne[i+1] = j;

}

```

* 使用两个指针 `i` 和 `j` 遍历字符串 `s`。

* 当 `s[i+1]` 与 `s[j+1]` 不相等时，`j` 指针回溯到 `ne[j]`。

* 当 `s[i+1]` 与 `s[j+1]` 相等时，`j` 指针前进一位。

* `ne[i+1]` 记录了 `s[0:i]` 与 `s` 的最长公共前缀的长度。

注意事项:

参考代码:

#include <iostream>

#include<cstring>

#include<stack>

using namespace std;

const int N=4e5+10;

char s[N];

int ne[N] ;

stack<int> st;

int main()

{

         while(cin >> s+1)

         {

                 //计算字符串s的next数组,模板背！

                 ne[0] = ne[1] = 0;

                 int len = strlen(s+1);

                 for(int i = 1,j = 0;i < len;i++)

                 {

                         while(j && s[i+1] != s[j+1]) j = ne[j];

                         if(s[i+1] == s[j+1]) j++;

                         ne[i+1] = j;

                 }

                 //len是必然可行的长度,即一种情况

                 st.push(len);

                 while(ne[len] != 0)

                {

                         st.push(ne[len]);

                         len = ne[len];

                 }

                 //输出

                 while(!st.empty())

                {

                     cout << st.top() << " " ;

                     st.pop();

                 }

                 cout <<endl;

         }

         return 0;

}