SPOJ HACKING

题意:给出一个长为 n 的,由字母表中前 k 个小写字母组成的字符串 s.求一个长度为m的字符串,要求该串也只能由字母表前 k 个小写字母组成,且其不能是 s 的子串.

[cpp]
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int N = 10010;
char s[N];
int a[100];
bool vis[N*40];
void print(int x,int m,int k)
{
    if(m==0)
    {
        return ;
    }
    print(x/k,m-1,k);
    printf("%c",x%k+'a');
}
int main(void)
{
    int T,n,m,k;
    scanf("%d",&T);
    while(T--)
    {
        memset(vis,0,sizeof(vis));
        scanf("%d%d%d",&n,&m,&k);
        scanf("%s",s);
        if(k==1)
        {
            for(int i=0;i<m;i++)
            {
                printf("%c",'a');
            }
            printf("\n");
        }
        else
        {
            int sum=1;
            int m1=0;
            while(sum<=n)    //算k^m1<=n;
            {
                m1++;
                sum*=k;
            }
            if(m1>m) m1=m;
            a[0]=1;
            for(int i=1;i<=m1;i++)
            {
                a[i]=a[i-1]*k;
            }
            int ans=0;
            for(int i=0;i<m1;i++)
            {
                ans=ans*k+s[i]-'a';
            }
            vis[ans]=1;
            for(int i=m1;i<n;i++)
            {
                ans-=a[m1-1]*(s[i-m1]-'a');
                ans=ans*k+s[i]-'a';
                vis[ans]=1;
            }
            for(int i=0;;i++)
            {
                if(vis[i]==0)
                {
                    print(i,m1,k);
                    printf("\n");
                    break;
                }
            }
        }
    }
    return 0;
}

补充：软件开发 , C++ ,