kmp模式匹配 注：string空格无效（可直接在源程序初始化串）.txt

来自「方便快捷地实现目标的查找」· 文本 代码 · 共 51 行

#include "stdafx.h"
#include "string.h"
#include <iostream>
using namespace std;
int next(string &T,int &n)
{
 if(n==0) return -1;
 else if(n>1)
 {
  int i=0;
  int h=n/2+n%2;
  int g=0;
  while(h<n)
  {if(T[i]==T[h]) {i++;h++;g++;}
   else {h=h-i+1;i=0;g=0;}
  }
  return g;
 }
  else return 0;
}
int indexKMP(string s,string t,int pos)
{int i=pos;
 int j=0;
 while(i<s.length()&&j<t.length())
 {
  if(s[i]==t[j]) {i++;j++;}
  else j=next(t,j);
  if(j==-1) {i++;j++;}
 }
 if(j==t.length()) return i-t.length()+1;
 else return 0;
}
int main(int argc, char* argv[])
{string a,b;
 char *c,*d;
 c=new char;
 d=new char;
 cout<<"The main string is:  ";
 cin>>c;
 a=c;
 cout<<"The mode string is:  ";
 for(int i=0;i<20;i++)
 {
 cin>>d;
 b=d;
  cout<<indexKMP(a,b,0)<<endl;
  cout<<"Please input another mode-string :  ";
 }
	return 0;
}