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