大きな話のデータ構造——KMPアルゴリズム（まだ問題があります）
2348 ワード
http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.
/*#include<iostream>
#include <string>
using namespace std;
int count_same_char(string T,int j);
void get_next(string T,int *next)
{
int j=1;
next[1]=0;
for(int k=2;k<=T.size();++k)
{
next[k]=count_same_char(T,k)+1;
}
}
// T 0 j-1 ，
// 0
int count_same_char(string T,int j)
{
j=j-1;
int cout_number=0;
int director=0;
for(int i=(j/2);i>=1;i--)//
{
for(int k=0;k<i;k++)
{
if(T[k]!=T[j-i+k])
{director=0;break;}
director=1;
}
if(director==1)
{cout_number=i;break;}
}
return cout_number;
}
int main()
{
string T="ababaaaba";
int next[10];
get_next(T,next);
for(int i=1;i<=T.size();++i)
{
cout<<next[i]<<' ';
}
cout<<endl;
/*string T="abcabx";
cout<<count_same_char(T,6)<<endl;
*/
/*
system("pause");
return 1;
}*/
#include<iostream>
#include <string>
using namespace std;
int get_number(string T,int j);
void get_char_number(string T,int *next)
{
next[0]=0;
int K=T.size();
for(int i=1;i<K;i++)
{
next[i]=get_number(T,i);
}
}
int get_number(string T,int j)
{
int count_number=0;
int i,k,temp;
for(k=(j+1)/2;k>=1;k--)
{
temp=0;
for(i=0;i<k;i++)
{
if(T[i]!=T[j-k+i+1])
{temp=1;break;}
}
if(temp==0)
{count_number=k;break;}
}
return count_number;
}
int KMP(string S,string T)
{
int next[100];
int result[100];
get_char_number(T,next);
if(T.size()>S.size())
return -1;
int i=0;// S
while(i<=(S.size()-T.size()))
{
int j,temp=1;
for(j=0;j<T.size();j++)
{
if(T[j]!=S[i+j])
{temp=0;break;}
}
if(temp=1)
return i;
if(j==0)
i++;
i=i+j-next[j-1];
}
return -1;
}
int main()
{
/*
string T="jkl";
//cout<<get_number(T,4)<<endl;
int next[10];
get_char_number(T,next);
for(int i=0;i<T.size();i++)
cout<<next[i]<<' ';
cout<<endl;
*/
string S="fghjkl";
string T="jkl";
cout<<KMP(S,T)<<endl;
system("pause");
return 1;
}