字符串匹配算法
方法一：朴素法：扫描待匹配字符串找出所有匹配子字符串，方法简单直接，这里省略代码
方法二：字符串匹配之rabin karp算法
用到的结论：（X*Y）%Q = （（X%Q）*Y）%Q
/*Filename:rabin_karp_matcher.cpp */
#include<iostream>
#include<string.h>
#include<math.h>
using namespace std;
int chartoint(char in){//字符转换成数字函数
int m = in - '0';
return m;
}
void rabin_karp_matcher(char *t,char*p,int d,int q){//字符串匹配函数：t待匹配字符串，p目标字串，d进制数，q模数，为了简单主要针对字符串中字符都是数字
int n = strlen(t);
int m = strlen(p);
int h = int(pow(d,m - 1))%q;
int p0 = 0;
int t0 = 0;
for(int i = 0;i < m;++i){//processing
p0 = (d*p0 + chartoint(p[i]))%q;
t0 = (d*t0 + chartoint(t[i]))%q;
}
for(int j = 0;j < (n - m);++j){//matching
if(p0 == t0){
bool flag = true;
for(int k = 0;k < m;++k){
if(t[j + k] != p[k]){
flag = false;
}
}
if(flag == true){
cout<<"matches at:"<<j<<endl;//匹配，返回匹配字串首字符位置
}
}
if(j < (n - m - 1)){
t0 = (d*((q - 1)*q + t0 - chartoint(t[j])*h) + chartoint(t[j + m]))%q;
}
}
}
int main(){
char *t = "1234567823452345234523459";
char *p = "2345";
rabin_karp_matcher(t,p,10,11);
return 0;
}
方法三：字符串匹配的有限自动机算法
/*Filename:finite_automation_matcher.cpp */
#include<iostream>
#include<string.h>
using namespace std;
bool str_equal(char *P,int k,char*T,int i){//比较T【i-k,...,i】是否与P【0,...,k】相等（P是否T后缀），相等返回true否则返回false
int count = 0;
while((count < k)&&(P[count] == T[i + count - k])){
++count;
}
if(count == k){
return true;
}else{
return false;
}
}
int delata(int q,int i,char *P,char *T){//计算字符串T【0,...，i-1】添加字符T[i]后，其后缀里面是P【0，...,q】前缀的那些后缀的最长的那个的长度（已知P【0,...,k-1】是T【0,...,i-1】的后缀）
if(P[q] == T[i]){
return q + 1;
}else{
int k = q;
while((k >= 1)&&(!str_equal(P,k,T,i))){
--k;
}
return k;
}
}
void finite_automation_matcher(char *T,char *P){//有限自动机匹配算法函数
int m = strlen(P);
int n = strlen(T);
int q = 0;
for(int i = 0;i < n;++i){
q = delata(q,i,P,T);
cout<<q<<endl;//输出当前q值（当前最长匹配后缀长度）
if(q == m){
cout<<"matches at:"<<i - m + 1<<endl;
q = 0;
}
}
}
int main(){
char *test1 = "123456";
char *test2 = "5511111123456551123456123456123456";
finite_automation_matcher(test2,test1);
return 0;
}
方法四：KMP算法
/*Filename:KMP.cpp*/
#include<iostream>
#include<string.h>
using namespace std;
/*定义：
*
* （1）next[0]= -1 意义：任何串的第一个字符的模式值规定为-1。
*
* （2）next[j]= -1 意义：模式串T中下标为j的字符，如果与首字符
*
* 相同，且j的前面的1—k个字符与开头的1—k
*
* 个字符不等（或者相等但T[k]==T[j]）（1≤k<j）。
*
* 如：T=”abCabCad” 则 next[6]=-1，因T[3]=T[6]
*
* （3）next[j]=k 意义：模式串T中下标为j的字符，如果j的前面k个
*
* 字符与开头的k个字符相等，且T[j] != T[k] （1≤k<j）。
*
* 即T[0]T[1]T[2]。。。T[k-1]==
*
* T[j-k]T[j-k+1]T[j-k+2]…T[j-1]
*
* 且T[j] != T[k].（1≤k<j）;
*
* (4) next[j]=0 意义：除（1）（2）（3）的其他情况。
*/
int *compute_next(char *T){//计算next数组
int n = strlen(T);
int *next = new int[n];
int k = 0;
next[0] = -1;//case 1
for(int j = 1;j < n;++j){
if(((T[j] == T[0])&&(k == 0))||((k != 0)&&(T[k] == T[j])&&(T[k] == T[0]))){//case 2
next[j] = -1;
}else if((k != 0)&&(T[j] != T[k])){//case 3
next[j] = k;
}else{//case 4
next[j] = 0;
}
if(k == 0){
if(T[j] == T[0]){
++k;
}
}else{
if(T[j] == T[k]){
++k;
}else if(T[j] == T[0]){
k = 1;
}else{
k = 0;
}
}
}
return next;
}
void KMP(char *T,char *P){
int m = strlen(P);
int n = strlen(T);
int j = 0;
int *next = compute_next(P);
for(int i = 0;i < n;++i){
while((j > 0)&&(P[j] != T[i])){
j = next[j];
}
if(j < 0) {
++j;
++i;
}
if(P[j] == T[i]){
++j;
}
cout<<j<<endl;//显示当前匹配长度
if(j == m){
cout<<"matches at:"<<i - m + 1<<endl;
j = 0;
}
}
}
int main(){
char *P = "ababcaabc";
char *T = "dfgababcaabcfjababcaabccdsababag";
cout<<T<<endl;
KMP(T,P);
return 0;
}