toj_2939.cpp

来自「Tianjin University Online Judge 的80多道题目 」· C++ 代码 · 共 44 行

#include<cstdio>
#include<cstring>
#define MAXLEN 100100
#define MAXNUM 1000000007
char s[ MAXLEN ] , len;
int a[ MAXLEN ] , chP[ 255 ] , p[ MAXLEN ];

int main()
{
    int i , j , k , testCase , tmp;
    
    char ch;
    scanf( "%d" , &testCase );
    while ( testCase-- ){
        scanf( "%s" , s );
        len = strlen( s );
        for( ch = 0; ch < 127; ch++ )
            chP[ ch ] = -1;
        
        for( i = 1; i <= len ; i++ ){
            p[ i ] = chP[ s[ i - 1 ] ];
            chP[ s[ i - 1 ] ] = i;
        }
        a[ 0 ] = 1;
        a[ 1 ] = 2;
        for( i = 2; i <= len; i++ ){
            if( p[ i ] == -1 )
                tmp = 2 * a[ i - 1 ];
            else
                tmp = 2 * a[ i - 1 ] - a[ p[ i ] - 1 ];
            if( tmp >= MAXNUM )
                tmp %= MAXNUM;
            a[ i ] = tmp;
        }
        printf( "%d\n" , a[ len ] );
    }
    return 0;
}