POJ3461-串匹配-经典的KMP

本文主要是介绍POJ3461-串匹配-经典的KMP，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目：题目链接

 

题意：就是给出母串，求出字串在母串中出现的位置；

 

经典的KMP算法：

 

#include <iostream>
#include <cstdio>
#include <string>
#include <string.h>
#include <map>
#include <vector>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <queue>
#include <set>
#include <stack>
#include <functional>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <numeric>
#include <cassert>
#include <bitset>
#include <stack>
#include <ctime>
#include <list>
#define INF 0x7fffffff
#define max3(a,b,c) (max(a,b)>c?max(a,b):c)
#define min3(a,b,c) (min(a,b)<c?min(a,b):c)
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;int caseNum,len1,len2, next[10005];
char mod[10005], s[1000005];void getnext()
{int i, j;next[1] = 0;j = 0;for(i = 2; i <= len2; i++){while(j > 0 && mod[j+1] != mod[i])j = next[j];if(mod[j+1] == mod[i])j++;next[i] = j;}
}int KMP(int pos = 1)
{int i,j,k;getnext();i = pos,k = 0,j = 0;while(i <= len1){while(j > 0 && mod[j+1] != s[i])j = next[j];if(mod[j+1] == s[i]){j++;if(j == len2)k++;}i++;}return k;
}int main()
{scanf("%d", &caseNum);mod[0] = 'Z', s[0] = 'H';while(caseNum--){scanf("%s%s", mod+1, s+1);len1 = strlen(s) - 1;len2 = strlen(mod) - 1;printf("%d\n", KMP());}return 0;
}

 

这篇关于POJ3461-串匹配-经典的KMP的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---