字符串连续出现次数最多的子串


#include "stdafx.h"
#include<iostream>
#include<string>
#include<math.h>
#include<vector>

using namespace std;
pair<int,string> getMaxSub(string &str){
    int len = str.length();
    vector<string> substrs;
    for(int i = 0 ; i < len ; i ++){
        cout<<str.substr(i,len-i)<<endl;
        substrs.push_back(str.substr(i,len-i));
    }
    int maxcount = 1;
    int count = 1;
    string substrtmp;
    for(int 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)){
                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;
                    substrtmp = substrs[i].substr(0,j-i);
                }
            }
        }
    }
    return make_pair(maxcount,substrtmp);
}
int _tmain(int argc, _TCHAR* argv[])
{
    string str("abcabcabc");
    pair<int,string> rs;
    rs = getMaxSub(str);
    cout<<rs.second<<rs.first<<endl;
    return 0;
}

abcabcabac

bcabcabc

cabcabc

abcabc

bcabc

cabc

abc

bc

c

循环比较第i个子串和j个子串的前面j-i个字符的异同，相同继续循环比较第k=j+j-i到第len，以j-i为步长的前面j-i个字符的异同。