寻找一个字符串连续出现最多的子串的方法(转)

算法描述
首先获得后缀数组，然后
1.第一行第一个字符a,与第二行第一个字符b比较，不等，则
2.第一行前两个字符ab，与第三行前两个字符cb比较，不等，则
3.第一行前三个字符abc,与第四行前三个字符bcb比较，不等，则
4.第一行前四个......
上述过程就相当于在原始字符串中，
第一趟，a与b比较，ab与cb比较，abc与bcb比较，abcb与cbca比较，abcbc与bcabc比较，abcbcb与cabc比较......
第二趟，b与c比较，bc与bc比较（相等，则继续向后取长度为2的子串比较，碰到不等为止，本例中因碰到ab停止），bcb与cbc比较......
第三趟，c与b比较，cb与cb比较（相等），cbc与bca比较......
......
使用后缀数组方便编程实现

//vs2005
#include "stdafx.h"
#include <iostream>
#include <vector>
#include <utility>
#include <string>
using namespace std;

pair<int,string> fun(const string &str)
{
	vector<string> substrs;
	int maxcount=1,count=1;
	string substr;
	int i,len=str.length();
	for(i=0;i<len;++i)
	{
		substrs.push_back(str.substr(i,len-i));//取子串 
		cout<<substrs[i]<<endl;
	}
		
	for(i=0;i<len;++i)
	{
	    for(int j=i+1;j<len;++j)
	    {
	        count=1;
	        if(substrs[i].substr(0,j-i)==substrs[j].substr(0,j-i))//(j-i)确定循环节的长度，存在循环子串
	        {
		++count;
		for(int k=j+(j-i);k<len;k+=j-i)//进一步寻找循环节
		{
		    if(substrs[i].substr(0,j-i)==substrs[k].substr(0,j-i))
			++count;
		    else
			break;
		}
		if(count>maxcount)
		{
		    maxcount=count;
		    substr=substrs[i].substr(0,j-i);
		}
	        }
	    }
	}
             return make_pair(maxcount,substr);
}

int _tmain(int argc, _TCHAR* argv[])
{	string str;
	pair<int,string> rs;

	str="abcbcbcabc";
	rs=fun(str);
	cout<<rs.second<<':'<<rs.first<<endl;

	return 0;
}