当先锋百科网

首页 1 2 3 4 5 6 7

poj_3032_Card Trick

题目大意：输入n，nc，nc代表有nc中字符，n代表需要找的字串额长度，例如n=3，nc=4，字符串为daababac

则不同的字串有"daa"; "aab"; "aba"; "bab"; "bac". 五种，输出5即可

假设字符集合构成的子串数量最大不超过1600万 

//思路，哈希,NC进制,NC个字符每个对应一个数字,再将字串转化为十进制即可

View Code 
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
using namespace std;

#define N 16000010

char str[N];
int ans[N];

int main()
{
    int n,m,len,sum,num[300],t,i,j;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        scanf("%s",str);
        len=strlen(str);
        memset(num,0,sizeof(num));
        memset(ans,0,sizeof(ans));
        for(i=0,t=1;i<len;i++)    //NC个字符每个对应一个数字
        {
            if(!num[str[i]])
                num[str[i]]=t++;
        }
        for(i=0,sum=0;i<len-n+1;i++)
        {
            t=0;
            for(j=i;j<n+i;j++)    //字串转化为十进制
            {
                t=t*m+num[str[j]];
            }
            if(!ans[t])    //如果字串已经出现过，则不再记数
            {
                sum++;
                ans[t]=1;
            }
        }
        printf("%d\n",sum);
    }
    return 0;
}

转载于:https://www.cnblogs.com/pcoda/archive/2012/05/05/2484866.html