|算法讨论|KMP 学习笔记

2019-11-11 05:09:47

字体：大中小

来源：转载

供稿：网友

输入两个字符串s1和s2，输出s2在s1中出现的位置(位置从0开始) input

abcdefghidefdddeeeffdefeddef

output

3920

实质上是MP算法

#include<cstdio> #include<algorithm> #include<cstring> #define ms(i,j) memset(i,j, sizeof i); using namespace std;char s1[1000000 + 5], s2[1000 + 5]; int next[1000 + 5];int n,m; void getNext()//获得失配函数 { next[0] = 0; next[1] = 0; for (int i=1;i<m;i++) { int j = next[i]; while (j && s2[i]!=s2[j]) j = next[j]; next[i+1] = ((s2[i]==s2[j]) ? (j+1) : (0)); }}void kmp()//在s1里找s2 { getNext(); int j = 0; for (int i=0;i<n;i++) { while (j && s1[i]!=s2[j]) j = next[j]; if (s1[i]==s2[j]) j++; if (j==m) PRintf("%d/n", i-m+1); }}int main() { scanf("%s%s", s1, s2); n = strlen(s1), m = strlen(s2); kmp(); return 0; }

KMP求字符串中的最短周期(循环节)： poj 2406 Power Strings

#include<cstdio> #include<algorithm> #include<cstring> #define ms(i,j) memset(i,j, sizeof i); using namespace std;const int MAXN = 1000000 + 5;int n;char s[MAXN];int f[MAXN];int main() { while (scanf("%s", s)&&(s[0]!='.')) { n = strlen(s); f[0] = f[1] = 0; for (int i=1;i<n;i++) { int j = f[i]; while (j && s[i]!=s[j]) j = f[j]; f[i+1] = (s[i]==s[j]) ? (j+1) : (0); } int ans = n-f[n]; if (n%ans==0) ans = n/ans; else ans = 1; printf("%d/n", ans); } return 0; }

上一篇：Leetcode 153. Find Minimum in Rotated Sorted Array

下一篇：JVM内存的那些事