本文主要是介绍FZU 2122(KMP),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
/*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;}elseh=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++;}elsej=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次 但是最后还是被我弄明白了,感觉还是不错的。故此下次一定要看清题目
*/
这篇关于FZU 2122(KMP)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!