字符串最大/小表示法

例题 HDU 3374 String Problem()

问题分析

求 循环节用kmp 最小最大表示法直接套用模板
最小/大表示法:开两个位置坐标 参数 i,j以及 跨度k(自己瞎起的名字,感觉很合适 噗...)
利用while循环进行多级跳转比较(每一个位置为首字符串所有都比较一遍 i,j 各作为一个字符串的首位置 );还是看代码解析吧 ^_^
最好是自己对着代码推一遍例子(" ABCAACAAA ")立马就能明白了

AC代码如下

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
const int maxx=1e6+10;
int nexx[maxx],len;
char s[maxx];
//貌似scanf()输入字符串时只能用 char型数组
//及时使用s.c_str()输入 也是转换成char[]型  
void ge()//kmp 求next[]数组 
{
    int i=0,j=-1;
    nexx[0]=-1;
    while(i<len){
        if(j==-1||s[i]==s[j]){
            i++,j++;
            nexx[i]=j;
        }
        else
        j=nexx[j];
    }
}
int min_max(int flag){//字符串最大最小表示法 
    int i=0,j=1,k=0;//位置参数 i,j;跨度 k 
    if(flag){ //判读 1最小表示法 0 最大 
    while(i<len&&j<len&&k<len){//完全比较 
        int t =s[(i+k)%len]-s[(j+k)%len];//循环回去 
        if(t==0)//相等 跨度++,相当于2参数都分别后移一位 
          k++;
        else{ //存在大小差异 
            if(t>0)  //前者 i位置 大于 j
                i+=k+1;//i变换为新的 最小下一位置 
            else
                j+=k+1;//i不变 j变换为较大一个下一位置 
            if(i==j)//i,j相等
                j++;
                        
            k=0;//跨度重置->i,j延续 
        }
      }
      return min(i,j);
      //取在前面的 
    }
    else
    {//同最小表示法 
    while(i<len&&j<len&&k<len){
        int t =s[(i+k)%len]-s[(j+k)%len];
        if(t==0)
          k++;
        else{
            if(t>0)
                j+=k+1;
            else
                i+=k+1;
            if(i==j)
                j++;
            k=0;
        }
      }
      return min(i,j);
    }    
}
int main()
{
    while(~scanf("%s",&s))
    {
     len =strlen(s);
     ge();
     int x=len-nexx[len];
     int num=1;
     if(len%x==0)
     num=len/x;
     printf("%d %d %d %d\n",min_max(1)+1,num,min_max(0)+1,num);
    }
    return 0;
}

例题 POJ 1200 Crazy Search

解题思路: 将N个字符串分别转换成数字 然后按照 NC进制转换为 10进制

运用了字符号串哈希

然后开一个标记数组进行标记(判定唯一性) 这样大大缩短了 时间
1600万-- 26个小写字母组合 再怎么 也不会太多
但是 不知道 到底是怎么推出的公式来的 进制转换为10进制(很神奇~~)

AC代码如下:

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<string.h>
#include<set>
using namespace std;
const int maxn=16000006;
char a[maxn];
bool hash[maxn];
int num[205];
int main() 
{
    int n,m;
    while(~scanf("%d%d",&n,&m))
    {
        memset(num,0,sizeof(num));
        memset(hash,0,sizeof(hash));
        scanf("%s",a);
        int len=strlen(a);
        int cnt=0;
        for(int i=0;i<len;i++)
        if(!num[a[i]])
        num[a[i]]=cnt++;
        int ans=0;
        for(int i=0;i<=len-n;i++)
        {
            int sum=0;
            for(int j=i;j<=i+n-1;j++)
            sum=sum*m+num[a[j]];
            if(!hash[sum])
            {
                ans++;
                hash[sum]=1;
            }
        }
        cout<<ans<<endl;
    }
     return 0;
}

字符串最大/小表示法 字符串哈希

原文：https://www.cnblogs.com/maxv/p/11606004.html