托米的咒语（序列自动机）

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 const int maxn = 3e3+10;
 5 const int inf=0x3f3f3f3f;
 6 #define rep(i,first,last) for(int i=first;i<=last;i++)
 7 #define dep(i,first,last) for(int i=first;i>=last;i--)
 8 char s[maxn];
 9 int nxt[maxn][30];
10 int now[30];
11 
12 void init(){
13     memset(now,-1,sizeof(now));
14     int len=strlen(s);
15     dep(i,len-1,0){
16         rep(j,0,25){
17             nxt[i][j]=now[j];
18         }
19         now[s[i]-‘a‘]=i;
20     }
21 }
22 
23 int main()
24 {
25     ios::sync_with_stdio(0);
26     cin.tie(0);
27     cout.tie(0);
28 
29     cin>>s;
30     init();
31     int cnt=0;
32     char ss[]="abcdefghi";
33     do{
34         int loc=now[ss[0]-‘a‘];
35         if( !~loc ) continue;
36         else{
37             bool flag=true;
38             int len=strlen(ss);
39             rep(i,1,len-1){
40                 loc=nxt[loc][ss[i]-‘a‘];
41                 if( !~loc ){
42                     flag=false;
43                     break;
44                 }
45             }
46             if( flag ) cnt++;
47         }
48     }while(next_permutation(ss,ss+9));
49     cout<<cnt<<endl;
50     return 0;
51 }