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

字元串最大/小表示法

例題 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;
}