社区讨论
40pts求助
P1308[NOIP 2011 普及组] 统计单词数参与者 1已保存回复 0
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 0 条
- 当前快照
- 1 份
- 快照标识符
- @milt60ax
- 此快照首次捕获于
- 2025/11/30 22:21 3 个月前
- 此快照最后确认于
- 2025/12/01 18:12 3 个月前
CPP
#include <bits/stdc++.h>
using namespace std;
const int N=15;
string p;
string s;
int fail[N];//p串的失配数组
bool is_big_letter(char c)
{
return ('A'<=c && c<='Z');
}
void init()//预处理失配数组
{
int m=p.size();
for(int j=1;j<m;j++)
{
int k=fail[j-1];
while(k>0 && p[j]!=p[k])
k=fail[k-1];
if(p[j]==p[k])
k++;
fail[j]=k;
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>p;
cin.ignore();//忽略第一行末尾空字符
getline(cin,s);
for(int i=0;i<p.size();i++)
if(is_big_letter(p[i]))
p[i]+=32;
for(int i=0;i<s.size();i++)
if(is_big_letter(s[i]))
s[i]+=32;
//KMP
init();
vector <int> res;
int n=s.size();
int m=p.size();
if(m==0 || n<m)
{
cout<<-1;
return 0;
}
int j=0;
for(int i=0;i<n;i++)
{
while(j>0 && s[i]!=p[j])
j=fail[j-1];
if(s[i]==p[j])
j++;
if(j==m)
{
res.push_back(i-m+1);
j=fail[j-1];
}
}
if(res.size()==0)
{
cout<<-1;
return 0;
}
else
cout<<res.size()<<" "<<res[0];
return 0;
}
代码如上。是我KMP写错了还是不能用KMP解决本题?
回复
共 0 条回复,欢迎继续交流。
正在加载回复...