pku 1200 Crazy Search(匹配,映射)

    技术2022-05-11  2

    #include <iostream> using namespace std; char str[1000000]; int chartoint[125];//存储字符和数字的映射 bool exist[16000000];//题目中有 maximum number of substrings formed by the possible set of characters does not exceed 16 Millions int main() { int N,NC,len,cnt=0,temp; scanf("%d%d",&N,&NC); scanf("%s",str); len=strlen(str); int k=0,i=0; memset(chartoint,0,sizeof(chartoint)); memset(exist,0,sizeof(exist)); while(k!=NC)//计算字符和数字(0,1,2,...,NC-1)的映射 { if(chartoint[str[i]]==0) chartoint[str[i]]=k++; i++; } for(i=0;i<len-N+1;i++) { temp=0; for(int j=0;j<N;j++)//因为数组在0到NC-1之间,可采用NC进制来计算每个串对应的值 { temp=temp*NC+chartoint[str[i+j]]; } if(!exist[temp]) cnt++,exist[temp]=true; } printf("%d/n",cnt); return 0; }  


    最新回复(0)