题目描述

blablabla

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

我用的trie树来存字符的

时间复杂度

参考文献

C++ 代码

#include<iostream>
using namespace std;
const int N=1e6+10;
int son[N][26],idx=0,cnt[26];
void insert(string str)
  {
    int p=0;
    for(int i=0;str[i];i++)
       {
         int u=str[i]-'a';
         if(!son[p][u]) son[p][u]=++idx;
         p=son[p][u];
       }

  }
void query(string str)
{
  int p=0;
  for(int i=0;str[i];i++)
     {
       int u=str[i]-'a';
       if(son[p][u])  
       {cnt[u]++;
       p=son[p][u];
     }

     }


}  
void quick_sort(int q[],int l,int r)
  { if(l>=r) return ;

    int x=q[(l+r)>>1];
    int i=l-1;
    int j=r+1;

    while(i<j)
      {
        do i++;while(q[i]>x);
        do j--;while(q[j]<x);
        if(i<j)
          {
            swap(q[i],q[j]);
          }
      }
      quick_sort(cnt,l,j);
      quick_sort(cnt,j+1,r);
  }
int main()
{
  string str;
  cin>>str;
  insert(str);
  query(str);
  quick_sort(cnt,0,25);
  int i; 
  for(i=0;cnt[i];i++);

  cout<<cnt[0]-cnt[i-1]<<" ";
  return 0;
}
blablabla

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla