解题思路:
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;
}
0.0分
1 人评分
C二级辅导-统计字符 (C语言代码)浏览:502 |
淘淘的名单 (C语言代码)答案错误???浏览:593 |
C语言程序设计教程(第三版)课后习题7.1 (C语言代码)浏览:512 |
剪刀石头布 (C语言代码)浏览:1747 |
C语言程序设计教程(第三版)课后习题1.6 (C语言代码)浏览:536 |
C语言程序设计教程(第三版)课后习题1.5 (C语言代码)浏览:468 |
C语言程序设计教程(第三版)课后习题1.5 (C语言代码)浏览:586 |
蚂蚁感冒 (C语言代码)浏览:768 |
数组与指针的问题浏览:716 |
整除问题 (C语言代码)浏览:518 |