首页 > 代码库 > 寻找子串位置<codevs>
寻找子串位置<codevs>
KMP板子题;
如果不会可以参考其他算法书
代码:
#include<iostream> #include<stdio.h> #include<stdlib.h> #include<cstring> using namespace std; string s1,s2; int len1,len2; int f[200000]; int main(){ cin>>s1>>s2; len1=s1.size(),len2=s2.size(); f[1]=f[0]=0; for(int i=1;i<len2;i++){ int j=f[i]; while(j&&s2[i]!=s2[j]) j=f[j]; if(s2[i]==s2[j]) f[i+1]=j+1; else f[i+1]=0; } int j=0; for(int i=0;i<=len1;i++){ while(j&&s1[i]!=s2[j]) j=f[j]; if(s1[i]==s2[j]) j++; if(j==len2) {printf("%d",i-j+2);break;} } return 0; }
寻找子串位置<codevs>
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。