FZU 2122(KMP)

谁借莪１个温暖的怀抱￠ 2022-08-10 14:57 27阅读 0赞

/*FZU 2122(简单字符串匹配，KMP算法)
    题目大意：
    就是给你3个字符串，第一个是模式串(用该串在文本串中去查找与之相同的串)即子串，
    第二个字符串是去替换在文本串（即主串）已找到相同的子串，从而最后输出产生的新串，
    如果没有找到，就原样输出文本串(即主串)，第三个字符串就是文本串(即主串)
    
    个人解题思想：
    就是用KMP算法找到子串在主串中的位置，然后首先用相同字符“~”去替换主串中找到的子串；
    运行产生的效果如下：
    输入：
    abc
    bc ab
    aaa aaabca 333Abcc##
    输出：
    aaa aa~~~a 333~~~c##
    再用一个for循环去扫描，如果出现‘~’，就立即输出需要替换上去的字符串，同时i=i+l2(l2为子串的长度)；
    最终输出结果：
    输入：
    abc
    bc ab
    输出：
    aaa aabc aba 333bc abc##
    */
    # include<iostream>
    # include<cstdio>
    # include<cstring>
    # include<algorithm>
    # include<cstdlib>
    # include<string>
    # include<cmath>
    using namespace std;
    int next[108];
    char p[108];
    char s[50008];
    char s1[1009];
    int l1,l2,l3;
    int i,j;
    int ans;
    void getnext()//KMP固定模板算法求next数组，这是KMP算法的核心
    {
        next[0]=-1;
        int i=0;
        int h=-1;
        while(i<l2)
        {
            if(h==-1||p[i]==p[h]||p[i]+32==p[h]||p[i]==32+p[i])//这里需注意大写小写都有为了统一全都变成小写
            {
                i++;
                h++;
                next[i]=h;
            }
            else
                h=next[h];
       }
    }
    void kmp(int n)//KMP函数
    {
        i=n,j=0;
        while(i<l1&&j<l2)
        {
            if(j==-1||s[i]==p[j]||p[j]+32==s[i]||p[j]-32==s[i])//同上
            {
                i++;
                j++;
            }
            else
                j=next[j];
            if(j==l2)
            {
                ans=i-l2;
                for(i=ans;i<ans+l2;i++)
                {
                    s[i]='~';//！！！！此处需要注意，该字符不能随便取，应取ASCII在[32,125]区间外的
                             //表示刚开始没看清题目，以为随便取，就取了‘*’结果WA 15次痛心呀，后来改成‘~’(ASCII为126)就AC了
                }
                j=next[j];
            }
        }
    
    }
    int main()
    {
       while(gets(p))
       {
           gets(s1);
           gets(s);
           l1=strlen(s);
           l2=strlen(p);
           getnext();
           kmp(0);
           for(i=0;i<l1;)
           {
               if(s[i]=='~') {printf("%s",s1);i+=l2;}
               else 
                {
                    cout<<s[i];
                    i++;
                }
           }
           cout<<endl;
       }
        return 0;
    }
    /*
    体会：
    虽然这道题WA 15次 但是最后还是被我弄明白了，感觉还是不错的。故此下次一定要看清题目
    */