请问如何计算最长不完全匹配子串的频率？

本文共计982个文字，预计阅读时间需要4分钟。

算法描述：找出一个长字符串中某个特定子串出现的频率，匹配的子串的上一字符和下一字符不需要严格相邻，只需满足在当前字符后即可。

算法要求：长字符串中的特定子串长度不超过100个字符。

算法描述：找出一个长字符串里的某个特定的子串出现的频率，匹配的子串的上一个字符和下一个字符不需要紧紧相邻，只要满足下一个字符在当前字符的后面就行。
算法要求：长字符串的宽度最长是500个字符。
输入：一个长字符串，宽度不能超过500个字符，一个短字符串
输出：短字符串在长字符串中出现的次数的后四位，不足四位左边填充零。

举例来说：在“wweell”字符串中找“wel”出现的次数，可以匹配到8次，应输出0008，每个匹配子串的索引序列分别如下
0,2,4
0,2,5
0,3,4
0,3,5
1,2,4
1,2,5
1,3,4
1,3,5

算法分析：能够想到的最直观的做法就是先在长串里找出短串的第一个字符所在的索引，组成一个首字符索引数组，然后分别处理每个首字符索引到长串末尾的子串。处理每个子串最蛮力的办法当然是递归，递归有几点要说明。
1、递归的每次必须要有前进的趋势，所以每次递归操作，要把当前扫描的长串的索引加一，以便下面的递归使用不同的上下文。
2、递归必须有明确的终止，当短串匹配完毕，应该是到达递归的最底层了，要递增一次匹配次数，并且return，为了调试方便，我们还打印出来了匹配短串在长串中的索引序列。
3、为了尽可能多的匹配结果，在我们匹配到一个字符的时候，除了把匹配字符加一，扫描索引加一继续递归外，我们还要进行一次匹配字符不加一，扫描索引加一继续递归。
4、当扫描到字串的最后一个字符时，一次匹配已经产生了，但你还要看看长串有没有扫描完，然后继续递归匹配子串的最后一个字符，以找到更多的匹配。

以上思路的实现代码很短，如下

internalclassProgram2{
privatestaticstringmath="welcometocnblogs";
privatestaticreadonlystring[]arr=newstring[math.Length];
privatestaticintret;
privatestaticstringtest_input="wweellccoommeetocnblogs";

privatestaticvoidMain(){
ret=0;
varwindex=newList<int>();
for(inti=0;i<test_input.Length;i++){
if(test_input[i]=='w')
windex.Add(i);
}
windex.ForEach(index=>{
arr[0]=index.ToString();
Handle(1,index+1);
});

stringstrRet=ret.ToString();
if(strRet.Length>4)
strRet=strRet.Substring(strRet.Length-4,4);
if(strRet.Length<4)strRet=strRet.PadLeft(4,'0');

Console.WriteLine(strRet);
Console.ReadKey();
}

privatestaticvoidHandle(intk,intstart){
for(inti=start;i<test_input.Length;i++){
if(k==math.Length-1&&test_input[i]==math[k]){
arr[k]=i.ToString();
Console.WriteLine(string.Join(",",arr));

++ret;
if(i<test_input.Length-1)
Handle(k,++i);
return;
}
if(test_input[i]==math[k]){
arr[k]=i.ToString();

Handle(++k,i);
Handle(--k,++i);
--i;
break;
}
}
}
}但效率不高，要是处理的长串是“wwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwweeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeellllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllcccccccccccccccccccccccccccccccccccccccccccccccccccccooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooommmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeee to cnblogs”，不知道嘛时候才能算完，而且算出来的ret可能会溢出，呵呵。
大家有什么好的思路，给表演一把，另外这个是code jam 2009的一个入围题目，大家有兴趣可以去玩玩。