/*算法描述:设置三层循环：第一层循环纪录子串从l到字符串总长度totallen的变化,用数组tempmax纪录每次

   循环返回的当次长度不重叠子串的最大个数；第二层循环是将子串的搜索划分成sizeofsub（当前子串长度）

   个小组，即总字符串中category，category+sizeofsub,category+2sizeofsub,... ...(category从0到

   sizeofsub-1变化)处的子字符串集合成一个小组，每个小组获得一个临时最大值，存于数组cate_max中；

   第三层循环实现第二层中每个小组中成员的历遍，以返回所需的临时不重叠子串的最大出现次数。*/

  #include<iostream.h>

  #include<string.h>

 

  int solve(const char*s,int l);

  int main(void)

    {

     const char*str="ababa";  

     int n=solve(str,3);

     cout<<n;

     cin.get(); 

    }

int solve(const char* s,int l)

    {

     int maxfrequence,sizeofsub,totallen=strlen(s),category,temp,k;

     

     int*tempmax=new int[totallen-l+1]; //数组tempmax的申明和初始化清空 

     for(int i=0;i<totallen-l+1;i++)  

         tempmax[i]=0; 

   

     for(sizeofsub=l;sizeofsub<totallen+1;sizeofsub++)  //第一层循环

        { 

               const int N=totallen/sizeofsub; //为下层循环准备而动态申请空间 

               char**sub=new char*[N];

               int*subnum=new int[N];

                

               int*cate_max=new int[sizeofsub]; 

               for(int i=0;i<sizeofsub;i++)

                     cate_max[i]=0;

for(category=0;category<sizeofsub;category++) //第二层循环

          {

                   for(int i=0;i<N;i++)

                      {

                      subnum[i]=0;  

                      sub[i]=NULL;

                      } 

                      int count=0;

                                          

         for(temp=category;temp<totallen;temp+=sizeofsub)                                

            { 

                                                                                      

                    const char* point=s+temp;  

                    for(k=0;k<count;k++)//如果与已有的某一纪录相同，则相应计数加一 

                    { 

                     if(memcmp(point,sub[k],sizeofsub)==0) 

                        { 

                         subnum[k]++; 

                         break;

                        } 

                    }

                    if(k==count)//否则新开辟空间存放新出现的子串 

                   {

                    sub[count]=new char[sizeofsub]; 

                    strncpy(sub[count],point,sizeofsub);

                    subnum[count++]=1;

                    }                                                                      

            } 

                     

                     cate_max[category]=subnum[0];   

                     for(k=0;k<N;k++)    

                     cate_max[category]=(subnum[k]>cate_max[category])?subnum[k]:cate_max[category];         

          }

                     

                    tempmax[sizeofsub-l]=cate_max[0];           

                    for(k=0;k<l;k++)    

                        tempmax[sizeofsub-l]=(cate_max[k]>tempmax[sizeofsub-l])?cate_max[k]:tempmax[sizeofsub-l];         

                    

                    

                    for(int k=0;k<N;k++)  //空间的释放 

                    delete[] sub[k]; 

                    delete[] sub;

                    delete[] subnum;

                    delete[] cate_max;

                    

         if(tempmax[sizeofsub-l]>=totallen/(sizeofsub+1))

            break;

      }

      

     maxfrequence=tempmax[0];

     for(k=0;k<totallen-l+1;k++)    

        maxfrequence=(tempmax[k]>maxfrequence)?tempmax[k]:maxfrequence;         

     delete[]  tempmax; 

     return maxfrequence; 
}

//编译环境 VC6.0
int solve(const char* s, int l)
{
    char* temp;
    int len = strlen(s);      //字符串长度
    int n=0;                  //重复次数
    int maxn = 0;             //最大重复次数
    int pos;                  //匹配开始位置
    int index;                //匹配成功位置
    int i, j, m;              //循环变量
    for(i=l; i<=len; i++)     //字串长度循环
    {
        temp = new char[i+1];
        temp[i] = '\0';
        for(j=0; j<=len-i; j++)//依次提取字串循环
        {
            n = 0;             //初始化为0
            //从s中提取长度为i，且从s[j]开始的字符串
            for(m=j; m<j+i; m++)
            {
                temp[m-j] = s[m];
            }
            
            pos = 0;
            while(pos <= len-i)
            {
                index = Index(s, temp, pos);
                if(index >= 0)
                {
                    n++;
                    pos = index + i;//防止重叠
                }
                else
                    break;
            }
            if(n > maxn)
            {
                maxn = n;
            }
        }
        delete[] temp;
    }

    return maxn;
}

int Index(const char* s,const char* t,int pos)
{
    int i=pos, j=0;
    while(i<strlen(s) && j<strlen(t))
    {
        if(s[i] == t[j])
        {
            ++i;
            ++j;
        }
        else
        {
            i = i-j+1;
            j = 0;
        }
    }
    if(j >= strlen(t))
        return i-strlen(t);//匹配成功
    else
        return -1;
}

//测试程序
#include <iostream>
#include <string>
using namespace std;
int solve(const char* s, int l);//接口函数
int Index(const char* s, const char* t, int pos);

void main()
{
    string str;
    int len, l;
    
    cout<<"Input a string"<<endl;
    cin>>str;
    cout<<"Input the value of l"<<endl;
    cin>>l;

    len = str.length();
    char* s = new char[len+1];
    strcpy(s, str.c_str());
    s[len] = '\0';
    
    int num = solve(s, l);
    cout<<"num = "<<num<<endl;
    delete[] s;
}

#include<iostream>

using namespace std;

int solve(const char *s, int l);
int KMP(const char *S, const char *T); //KMP模式匹配程序
void GetNextVal(const char *T, int next[]);//求模式串T的next函数值
int HowManyKMP(const char *S, const char *T);//计算总共有多少个匹配模式 

int main()
{
    char *s = "abcababc"; 

    cout << solve(s, 4) << endl;

    system("pause");
    return 0;
}

int solve(const char *s, int l)
{
    char *temp = new char[l+1];
    int len = strlen(s);
    int max = 0;
    
    for (int i=0; i<=len-l; ++i)
    {
        for (int j=0; j<l; ++j)//提取模式串temp 
            temp[j] = s[i+j];
        temp[l] = '\0';
        
        int num = HowManyKMP(s, temp);//cout << temp << ": "<<num << endl;
        if (max < num)
            max = num;
    }
    
    return max;
}

int HowManyKMP(const char *S, const char *T) //计算总共有多少个匹配模式 
{
    int sum = 0;
    int pos;
    const char *p = S; //用来遍历S的指针 

    while (p)
    {
        pos = KMP(p, T);
        if (pos == -1)
            break;
        else    //如果匹配继续判断，并累计匹配的个数 
        {
            ++sum;
            p += pos + strlen(T);
        }
    }
    return sum;
}

void GetNextVal(const char *T, int next[]) //求模式串T的next函数值
{ 
    // 求模式串T的next函数值并存入数组 next。
    int j = 0, k = -1; 

    next[0] = -1; 

    while (T[j] != '\0') 
    { 
        if (k == -1 || T[j] == T[k]) 
        { 
            ++j; 
            ++k; 
            if (T[j] != T[k]) 
                next[j] = k; 
            else 
                next[j] = next[k]; 
        }// if
        else 
            k = next[k]; 
    }// while
}

int KMP(const char *S, const char *T) //KMP模式匹配程序
{ 
    if (!S || !T || S[0]=='\0' || T[0]=='\0')
        return -1;//空指针或空串，返回-1。
    
    int len = strlen(T);    
    int *next = new int[len+1];
    
    GetNextVal(T, next);//求T的next函数值

    int i = 0, j = 0; 

    while (S[i]!='\0' && T[j]!='\0') 
    { 
        if (S[i] == T[j]) 
        { 
            ++i;// 继续比较后继字符
            ++j; 
        } 
        else if (next[j] == -1) 
        { 
            j = 0; 
            ++i; 
        }
        else    
            j = next[j];// 模式串向右移动
    }//while
     
    delete []next;
     
    if (T[j] == '\0') // 匹配成功
        return i - len;
    else 
        return -1;  
}

/*
用Dev-C++ 4.9.9.2编程环境编译C语言。
根据题目，“给出一个由小写字母组成的串s和一个不超过s的长度的正整数l，
求s所有长度不小于l的字串中在s中不重叠地重复出现次数最多的子串。
只要输出这个子串出现的次数就行了。”
我个人认为，求出l长度字串出现的字数，即为出现最多的次数。
其它大于l长度的字串出现次数小于等于l长度字串出现的次数。 
*/
#include <stdio.h>
#include <string.h>
#define M 100  /*定义数组s的大小*/
int solve(const char *s,int l)
{
 int n,i,j,a,b,c,max=1,t;
 char q[M],d[M];  /*q数组表示截取的子串；d数组表示从字母串按顺序截取l长度的字母串*/
 n=strlen(s);  /*n表示字母串的长度*/
 if(l<=n/2)  /*截取长度要小于等于总长度的一半*/
 {
  j=0;  /*从头开始截取*/
  while(j<=n-l)
  {
   for(i=j,c=0; i<l+j; i++,c++)
   { q[c]=s[i]; }
   q[c]='\0';
   t=1;  /*t表示本次q数组出现的次数*/
   b=j+l;  /*b表示从截取子串的后一位开始比较*/
   while(b<=n-l)
   {
    for(a=b,c=0; a<l+b; a++,c++)
    { d[c]=s[a]; }
    d[c]='\0';
    if(strcmp(q,d)==0) { t++; b+=l; }  /*q和d完全相等，刚向后跳过所要截取的l长度*/
    else b++;  /*q和d不相等，则进一位*/
   }
   if(max<t) max=t;  /*max表示所截取子串出现最多的次数*/
   j++;  /*向后一位截取*/
  }
 }
 return max;
}
int main(void)
{
 char s[M];
 int l,n;
 printf("Enter s: ");
 gets(s);  /*输入字母串*/
 n=strlen(s);  /*求字母串的长度*/
 printf("Enter l<=%d: ",n);
 scanf("%d",&l);  /*输入要截的子串长度*/
 if(l<=n)
 printf("%d\n",solve(s,l));  /*输出子串出现最多的次数*/
 else printf("error\n");
 system("pause");
 return 0;
}

class CNode{
private :
    int m_iLevel;
    int m_iCount;
    int m_iPrior;
    CNode* m_Node[26];
public:
    int GetLevel();
    int GetCount();
    int GetPrior();
    CNode* GetNode(int i);
    void SetLevel(int level);
    void AddCount();
    void SetCount(int count);
    void SetPrior(int prior);
    void Bring();
    CNode(int level);
    ~CNode();
};

int CNode::GetLevel()
{
    return m_iLevel;
}

int CNode::GetCount()
{
    return m_iCount;
}

int CNode::GetPrior()
{
    return m_iPrior;
}

CNode* CNode::GetNode(int i)
{
    return m_Node[i];
}
void CNode::SetLevel(int level)
{
    m_iLevel = level;
}

void CNode::SetCount(int count)
{
    m_iCount = count;
}

void CNode::AddCount()
{
    m_iCount ++;
}

void CNode::SetPrior(int prior)
{
    m_iPrior = prior;
}

void CNode::Bring()
{
    for(int i = 0;i<26;i++){
        m_Node[i] = new CNode(m_iLevel + 1);
    }
}

CNode::CNode(int level)
{
    m_iLevel = level;
    m_iCount = 0;
    m_iPrior = -1;
    for(int i = 0;i<26;i++){
        m_Node[i] = NULL;
    }
}

CNode::~CNode()
{
    for(int i = 0;i<26;i++){
        if(m_Node[i])
            delete m_Node[i];
    }
}

class CTree{
private :
    CNode* boot;    //根节点
    char* m_str;        //字符串
    int m_len;            //
    void ReadChar(int &pos,int &MaxCount,CNode** temp);
public:
    int solve();
    CTree(char* s,int l);
    ~CTree();
};

CTree::CTree(char* s,int l)
{
    m_str = s;
    m_len = l;
    boot = new CNode(0);
}

CTree::~CTree()
{
    delete boot;
}

void CTree::ReadChar(int &pos,int &MaxCount,CNode** temp)
{
    int k = m_str[pos] - 'a';
    for(int i=0;i<m_len;i++){
        if(i<=pos){
            if(temp[i]->GetNode(i) == NULL)
                temp[i]->Bring();
            temp[i] = temp[i]->GetNode(k);
            if(temp[i]->GetLevel() == m_len){
                if((pos - temp[i]->GetPrior()) >= m_len){
                    temp[i]->AddCount();
                    if(MaxCount < temp[i]->GetCount())
                        MaxCount = temp[i]->GetCount();
                    temp[i]->SetPrior(pos);
                }
                temp[i] = boot;
            }
        }
    }
}

int CTree::solve()
{
    int MaxCount = 0;
    int pos = 0;
    CNode** temp = new CNode* [m_len];

    for(int i = 0;i<m_len;i++)
        temp[i] = boot;
    
    for(;pos<strlen(m_str);pos ++)
        ReadChar(pos,MaxCount,temp);
    delete []temp;
    return MaxCount;
}

int solve(char* s,int l)
{
    if(strlen(s) < (2*l))
        return 1;
    CTree tree(s,l);
    return tree.solve();
}

ding