KMP算法

    今天在POJ上做水题3981，是读取一行字符串并将其中的you换成we输出。以前用c的时候都是用的gets()和char。现在用C++，就了解了下getline与string。

    getline用来获取一行，语法是getline(cin,str)，读到文件末尾就返回EOF。按照题目要求，将输入的数据保存在string str中，在str中寻找字符串you，string的find函数：str.find("you")，如果找到第一个you就返回you的开始位置，找不到就返回string::npos，记录这个位置为start，将start位置起的长度为3的内容换为we，然后从start+2开始继续寻找you，直到找不到you为止。

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

int main()
{
    string str;
    while(getline(cin, str))
    {
        int start = str.find("you");
        while(start != string::npos)
        {
            str.replace(start, 3, "we");
            start = str.find("you", start+2);
        }
        cout << str << endl;
    }
    return 0;
}

 

   参考boost文档库，其实string的find方法提供的是O(m*n)的效率，不是很高，在这里就引出了KMP算法，它的时间效率是O(n+m)。

 

   模式匹配过程是这样：

       当模式串t中的tj与主串中的si比较不相等时，若模式串中存在真子串"t0t1...tk-1"="tj-ktj-k+1...tj-1"，此时可以将模式串t按照k=next[j]的值右移，然后比较si与tk（仔细想想），若仍有si!=tk，则继续按照k=next[k]进行迭代，继续右滑，然后比较si与tk。这样的过程一直进行到k=0，此时，若仍有si!=t0，则比较si+1与t0。

next[j]的值有三种意思：

       当串有真子串，为k（0<k<j）；

       当串无真子串，为0；

       当j=0，为-1。

//返回值：模式串在主串中出现的位置。s为主串，t为模式串，start是从主串开始搜索的位置(从0开始)
int KMPIndex(int next[], char s[], char t[], int start)
{
	int slen = strlen(s);
	int tlen = strlen(t);
	int i = start,j = 0, v;
	while(i<slen&&j<tlen)
	{
		if(s[i] == t[j])
		{
			i++;
			j++;
		}
		else if(j == 0) i++;
		else j = next[j];
	}
	if(j == tlen) v = i - tlen;
	else v = -1;
	return v;
}

 

下面，来讨论求next[j]值的算法问题。从next[j]值的三种意思可以看出，next[j]值的计算是一个递推问题。设有next[j]=k，即在模式串t中存在"t0t1...tk-1"="tj-ktj-k+1...tj-1"，(0<k<j)，其中k为满足等式的最大值，则计算next[j+1]有两种情况：

(1) 若tk=tj，则有next[j+1] = next[j]+1 = k + 1;

(2) 若tk!=tj，则把模式串"t0t1...tk-1"向右移动至k = next[k]。若此时tk=tj，则表明在模式串t中有"t0t1...tk-1tk"="tj-ktj-k+1...tj-1tj"，因此有next[j+1] = next[next[j]] +1；若此时tk!=tj，则继续右移，以此类推，直到某此tk=tj，或某此比较有tk!=tj并且k=0，有next[j+1]=0。

 

//求子串T的next[j]的值保存在数组next中
void GetNext(char t[], int next[])
{
	int tlen = strlen(t);
	int j = 1, k = 0;
	next[0] = -1;
	next[1] = 0;
	while(j < tlen)
	{
		if(t[j] == t[k])
		{
			next[j+1] = k + 1;
			j++;
			k++;
		}
		else if(k == 0)
		{
			next[j+1] = 0;
			j++;
		}
		else
			k = next[k];
	}
}

 

   对于poj2406，首先求出串s对应的next数组后（串s的长度为n），构成s的字符串长度为d=n-next[n]（如果n%d==0，存在这样的构成），相应的重复次数为n/d。

 

#include <iostream>

const int MAX = 1000001;
char s[MAX];
int next[MAX];

void getNext(int len)
{
	int j = 1, k = 0;
	next[0] = -1;
	next[1] = 0;
	while(j < len)
	{
		if(s[k] == s[j])
		{
			next[j + 1] = k + 1;
			j++;
			k++;
		}
		else if(k == 0)
		{
			next[j + 1] = 0;
			j++;
		}
		else
			k = next[k];
	}
}

int main()
{
	int t;
	int length;
	while(true)
	{
		scanf("%s",s);
		if(s[0] == '.') break;
		length = strlen(s);
		getNext(length);
		t = next[length];
		if(length%(length-t))
			printf("1\n");
		else
			printf("%d\n",length/(length-t));
	}
	return 0;
}

 

 参考poj1961，2406，2752