社区讨论

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 条回复,欢迎继续交流。

正在加载回复...