数据结构实验之串一：KMP简单应用





Time Limit: 1000MS Memory limit: 65536K


题目描述

给定两个字符串string1和string2，判断string2是否为string1的子串。

输入

 输入包含多组数据，每组测试数据包含两行，第一行代表string1(长度小于1000000)，第二行代表string2（长度小于1000000），string1和string2中保证不出现空格。

输出

 对于每组输入数据，若string2是string1的子串，则输出string2在string1中的位置，若不是，输出-1。

示例输入

abc
a
123456
45
abc
ddd



示例输出

1
4
-1



///ACcode

#include <iostream>
#include <cstdio>
using namespace std;

const int maxn=10000010;
typedef struct
{
    char *top,*base;
    int Size;
    int len;
} String;

void Creat(String &s)  ///建串
{
    s.base=new char[maxn];
    s.top=s.base;
    s.Size=maxn;
    s.len=0;
}

void push(String &s,char c) ///入串...函数名有点眼熟...
{
    s.top++;
    *s.top=c;
    s.len++;
}

void add(String &s,char st[]) ///为了使 两个串 下标从零开始
{
    int i;
    for (i=0; st[i]; i++)
    {
        push(s,st[i]);
    }
}

void getnext(String &s,int next[]) /// 相当于KMP函数 其实就是和本身比较来寻找next[]数组;建议先看下面的KMP函数
{
    int i=1,j=0; ///j从 1 开始的话 next[2]=2;显然不符合next[]数组....
    next[1]=0;
    while(i<=s.len)
    {
        if (j==0||s.base[i] == s.base[j])
        {
            i++;
            j++;
            next[i]=j; /// 动态演示中很明显看出 前 j 个字符已经匹配
        }

        else
        {
            j=next[j]; /// 失配时 j“跳”到next[j]位置（也就是说next[j]之前的位置已经匹配）
        }
    }
}

void kmp(String &st,String &pt,int next[])  ///kmp ,st主串 pt模式串
{
    int i=1,j=1;
    while(i<=st.len && j<=pt.len)
    {
        if(j==0||st.base[i] == pt.base[j])
        {
            i++;
            j++;
        }
        else
        {
            j=next[j]; /// 失配时 j“跳”到next[j]位置（也就是说next[j]之前的位置已经匹配）
        }
    }
    if (j>pt.len) ///说明模式串pt匹配完成
    {
        cout<<i-pt.len<<endl;
    }
    else  ///串st遍历先完了,则pt不是st子串
    {
        cout<<"-1"<<endl;
    }
}

void  print(String &s) ///打印
{
    int i;
    for (i=1; i<=s.len; i++)
    {
        cout<<s.base[i];
    }
    cout<<endl;
}

int main()
{
    int next[maxn];
    char st[maxn],pt[maxn]; ///先数组存 主串 , 模式串
    while(cin>>st>>pt)
    {
        String s,p;  ///主串 , 模式串

        Creat(s);
        Creat(p);

        add(s,st);
        add(p,pt);

        getnext(p,next);
        kmp(s,p,next);
    }
    return 0;
}


如下图
 ↓  ↓ ↓ ↓当求next[4]时，前面绿色表示已经匹配，即a匹配   next[i]就等于j 也就是next[i-1]+1



 ↓  ↓ ↓ ↓同理 ，next[6]前面有 两个绿色表示已经匹配 next[i]=j (next[i-1]+1)
next[i]失配 模式串（下面那个串）j=next[j],继续寻找匹配的位置......




 ↓  ↓ ↓ ↓同理 next[8]也如此求  next[]等于1 表示紧挨着前面没有匹配成功的  2 表示1个  以此类推..

kmp.h
文件的建立
typedef int Status;

#define MAXSTRLEN 255

typedef struct 

{
char data[MAXSTRLEN+1];
int length;

}HString;



Status Concat(HString &T,HString S1,HString S2);

void StrAssign(HString &S,char cstr[]);

Status StrCopy(HString &T,HString S);

Status StrEmpty(HString S);

Status StrCompare(HString S,HString T);

Status StrLength(HString S);

Status ClearString(HString &S);

Status Concat(HString &S);

Status SubString(HString &Sub,HString S,int pos,int len);

int Index(HString S,HString T);

Status Replace(HString &S,HString T,HString V);

Status StrInsert(HString &S,int pos,HString T);

Status StrDelete(HString &S,int pos,int len);

Status DestroyString(HString &S);

Status Index_KMP(HString S,HString T);

void get_nextval(HString T,int nextval[]);

void DispStr(HString s);

void get_next(HString T,int next[]);

Status Index_KMP1(HString S,HString T);



KMPS.cpp 文件的建立



#include "stdafx.h"

#include "kmp.h"





Status Concat(HString &T,HString S1,HString S2)

{
int i,uncut;
if(S1.length+S2.length<=MAXSTRLEN)
{
T.length=S1.length+S2.length;
for(i=1;i<=S1.length;i++)

           T.data[i]=S1.data[i];
for(i=S1.length+1;i<=S1.length+S2.length;i++)
T.data[i]=S2.data[i-S1.length];
uncut=TRUE;
}
else if(S1.length<MAXSTRLEN)
{
for(i=1;i<=S1.length;i++)
T.data[i]=S1.data[i];

        for(i=S1.length+1;i<=MAXSTRLEN;i++)
T.data[i]=S2.data[i-S1.length];
T.length=MAXSTRLEN;
uncut=FALSE;
}
else
{

        for(i=1;i<=MAXSTRLEN;i++)
T.data[i]=S1.data[i];
uncut=FALSE;
}


return uncut;

}



void StrAssign(HString &S,char cstr[])

{

int i;
for (i=1;cstr[i-1]!='\0';i++)
S.data[i]=cstr[i-1];
S.length=i-1;

}



Status StrCopy(HString &T,HString S)

{
int i=0;
T.length=S.length;
while(S.data[i]!='\0')
{
T.data[i]=S.data[i];
}
return OK;

}



Status StrEmpty(HString S)

{
if(S.length==0&&S.data[1]=='\0')
return TRUE;
else
return FALSE;

}



Status StrCompare(HString S,HString T)

{

    
return OK;

}



Status StrLength(HString S)

{

return S.length;

}



Status ClearString(HString &S)

{
int i;
for(i=1;i<=S.length;i++)
S.data[i]='\0';
S.length=0;
return OK;

}



Status Concat(HString T,HString S1,HString S2)

{
int i;
T.length=S1.length+S2.length;
for(i=1;i<=S1.length;i++)

           T.data[i]=S1.data[i];
for(i=S1.length+1;i<=S1.length+S2.length;i++)
T.data[i]=S2.data[i-S1.length];
return OK;

}



Status SubString(HString &Sub,HString S,int pos,int len)

{
int i;
for(i=pos;i<=len;i++)
Sub.data[i-pos-1]=S.data[i];
Sub.data[0]=len;
return OK;

}



int Index(HString S,HString T) 

{
int i=1,j=0;
while (i<=S.length && j<T.length) 
{ if (S.data[i]==T.data[j])

{ i++;

j++;
}
else 
{ i=i-j+1;

j=0; 
}
}
if (j>=T.length)
return(i-T.length-1);

else
return(-1); 


}



Status Replace(HString &S,HString T,HString V)

{

    
return OK;

}



Status StrInsert(HString &S,int pos,HString T)

{
int i;

    HString P;
P.length=S.length+T.length;
for(i=1;i<=pos-1;i++)

        P.data[i]=S.data[i];
for(i=pos;i<=T.length;i++)
P.data[i]=T.data[i-pos+1];
for(i=pos;i<=S.length;i++)
P.data[i+T.length]=S.data[i];
for(i=1;i<=P.length;i++)
S.data[i]=P.data[i];
S.length=P.length;
return OK;

}



Status StrDelete(HString &S,int pos,int len)

{


HString P;
int i;

    P.length=S.length-len;
for(i=1;i<=pos-1;i++)

        P.data[i]=S.data[i];

    for(i=pos+len;i<=S.length;i++)
P.data[i-len]=S.data[i];
return OK;

}



Status DestroyString(HString &S)

{


free(S.data);
return OK;

}



Status Index_KMP(HString S,HString T)

{

   int nextval[MAXSTRLEN+1];

   get_nextval(T,nextval);

   int i,j;

   j=1;

   i=1;

   while(i<=S.length&&j<=T.length)

   {
  if(j==0||S.data[i]==T.data[j])
  {
  ++i;
  ++j;
  }
  else 
  {
  
  j=nextval[j];
  }

   }

   if(j>T.length)
  return i-T.length;

   else 
  return 0;

}



void get_nextval(HString T,int nextval[])

{
int i,j;
i=1;
nextval[1]=0;
j=0;
while(i<T.length)
{
if(j==0||T.data[i]==T.data[j])
{
++i;
++j;
if(T.data[i]!=T.data[j])
nextval[i]=j;
else
nextval[i]=nextval[j];

}
else 
j=nextval[j];
}

}

void DispStr(HString s)

{ int i;
if (s.length>0)
{ for (i=1;i<=s.length;i++)
printf("%c",s.data[i]);
printf("\n");
}

}



void get_next(HString T,int next[])

{

   int i,j;
i=1;

   next[1]=0;

   j=0;

   while(i<T.length)

   {
  if(j==0||T.data[i]==T.data[j])
  {
  ++i;
  ++j;
  next[i]=j;
  
  }
  else
  j=next[j];

   }

}



Status Index_KMP1(HString S,HString T)

{

   int next[MAXSTRLEN+1];

   get_next(T,next);

   int i,j;

   j=1;

   i=1;

   while(i<=S.length&&j<=T.length)

   {
  if(j==0||S.data[i]==T.data[j])
  {
  ++i;
  ++j;
  }
  else 
  {
  
  j=next[j];
  }

   }

   if(j>T.length)
  return i-T.length;

   else 
  return 0;

}


主函数所在的文件
#include "stdafx.h"

#include "kmp.h"



int main(int argc, char* argv[])

{
//printf("Hello World!\n");
int j,a;
int nextval[MAXSTRLEN+1],next[MAXSTRLEN+1];
HString s,t;
StrAssign(s,"abcabcdabcdeabcdefabcdefg");
StrAssign(t,"abcdeabcdefab");
printf("串s:");DispStr(s);
printf("串t:");DispStr(t);


get_nextval(t,nextval);
//由模式串t求出nextval值
get_next(t,next);
printf("    j   ");
for (j=1;j<=t.length;j++)
printf("%4d",j);
printf("\n");
printf(" t[j]   ");
for (j=1;j<=t.length;j++)
printf("%4c",t.data[j]);
printf("\n");


printf("\n");
printf(" nextval");
for (j=1;j<=t.length;j++)
printf("%4d",nextval[j]);
printf("\n");
printf("改进的KMP算法:\n");
a=Index_KMP(s,t);
printf("  t在s中的位置=%d\n",a);
printf("<------------------------------------------------------------>\n");
printf("    j   ");
for (j=1;j<=t.length;j++)
printf("%4d",j);
printf("\n");
printf(" t[j]   ");
for (j=1;j<=t.length;j++)
printf("%4c",t.data[j]);
printf("\n");
printf(" next   ");
for (j=1;j<=t.length;j++)
printf("%4d",next[j]);
printf("\n");


printf("旧版的KMP算法:\n");
a=Index_KMP1(s,t);
printf("  t在s中的位置=%d\n",a);

    system("pause");
return 0;

}

题目：从一个字符串找到最长的重复字符串并返回第一个字符的位置。

思路一：暴力，不做太多解释。

思路二：根据字符串的查找理所当然想到KMP，KMP的next数组，next[i]=k，从该字符串头结点开始的后k个结点与i结点往前k个字符串相同，很明显了。然后遍历再调整一下Getnext函数让其返回此次计算的最大值就行了。

#include <stdio.h>  
#include <string.h>  
#include <iostream>  
#include <algorithm>
#include <math.h>
#include <map> 
#include <queue>
#include <vector> 
#define PI acos(-1)
#define INF 1e18
#define inf 1e9
#define IOS ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define Si(i) scanf("%d",&i)
#define Pi(i) printf("%d\n",i);
#define ElemType int 
using namespace std ;
typedef long long ll;
typedef unsigned long long ull;
const int _max = 10005;
const ll mod = 1e9+7;
char str[_max];
int next[_max];
int getNext(char *str,int *next){  
    int len=strlen(str);  
    int index=0;  
    int k=-1;  
    next[0]=k;  
    int max=0;  
    while(index<len){  
        if(k == -1 || str[index] == str[k]){  
            k++;  
            index++;  
            next[index]=k;  
            if(k>max)	max = k;
        }  
        else  
            k=next[k];  
    }
	for(int i = 0 ; i < len ; i++)
		cout<<next[i]<<' ';
	cout<<endl;
    return max;  
}  
  
int main(){  
    while(cin>>str){
	    int max=0;
	    int nextMax;   
	    int maxIndex;
	    int len=strlen(str);   
	    for(int index=0;index<len-1;index++){  
	        nextMax=getNext(str+index,next); 
	        if(nextMax>max){  
	            max=nextMax;  
	            maxIndex=index;  
	        }  
	    }  
		cout<<maxIndex<<endl; 	
		for(int i = 0 ; i < max ; i++)
			cout<<str[maxIndex+i];
		cout<<endl;
    }  
    
    return 0;  
}  

 

今天下午实现了KMP算法


这个算法算是奇妙，本机器看了10遍左右才基本理解
算法的核心就是求出next，再依次根据next跳转，这样就能线性地匹配出字符串
这里推荐一篇博文http://blog.csdn.net/joylnwang/article/details/6778316，joylnwang说得很好，深入浅出，只是在next数组是从1开始的，而pattern是从0起始，这也算是前几次学习的时候没有理解的地方
今天下午写的代码也应用了template，也能兼容其他的数据类型，练习了一下C++
<pre name="code" class="cpp">#include "iostream"
#include "string"
using namespace std;

template <class T>
class KPM
{
private:
	int MAX_P;
	int MAX_T;
	int *next = new int[MAX_P + 1];
	T	*pattern = new T[MAX_P + 1];
	T	*target = new T[MAX_T];
	int* BuildNext();
public:
	KPM(T *pat, int max_p, T *tar , int max_t)
	{
		MAX_P = max_p;
		MAX_T = max_t;
		pattern = pat;
		target = tar;
	}
	int GetResult();
};

template <class T>
int* KPM<T>::BuildNext()
{
	int i = 1;
	int t = 0;
	next[i] = 0;
	while (i < MAX_P)
	{
		while (t > 0 && pattern[i - 1] != pattern[t-1])//依次向前找到next，确定f(t)
		{
			t = next[t];
		}
		++t;
		++i;
		if (pattern[i - 1] == pattern[t - 1])
		{
			next[i] = next[t];
		}
		else
		{
			next[i] = t;
		}
	}
	for (int i = 1; i < MAX_P +1 ; i++)
	{
		cout << next[i] << " ";
	}
	cout << endl;
	return next;
}

template <class T>
int KPM<T>::GetResult()
{
	BuildNext();
	int t = 0;
	int p = 0;
	while (t < MAX_T && p < MAX_P + 1)
	{
		if (p == 0 || target[t] == pattern[p - 1])
		{
			cout << target[t] << " " << t << " " << pattern[p] << " " << p << endl;
			++t;
			++p;
		}
		else
		{
			p = next[p];
		}
	}
	if (p == MAX_P + 1)
	{
		cout << "从主串的第" << t - MAX_P + 1 << "个数开始匹配" << endl;
		return t - MAX_P;
	}
	else
	{
		cout << "主串无可匹配的子串" << endl;
		return 0;
	}
}

int main()
{
	char *P = "abcabcacab";
	char *T = "babcbabcabcaabcabcabcacabc";
	KPM<char> *a = new KPM<char>(P, 10, T, 26);
	a -> GetResult();
	system("pause");
}