牛客网 牛客练习赛 23 D 托米的咒语

#include<algorithm>
#include<vector>
#include<cstring>
#include<iostream>
#define endl "\n"
using namespace std;
vector<int> g[10];
int s[3000+10];
int a[10]={0,1,2,3,4,5,6,7,8};
int main(){
  string str;
  while(cin>>str){
    int len=str.length();
    for(int i=0;i<len;i++){
      s[i]=str[i]-'a';//abcdefghi  对应012345678 
      g[s[i]].push_back(i);//存样本中的下标 
    }
    int ans=0;
    do{
      bool f=true;
      int p=-1;
      for(int i=0;i<9;i++){
        p=lower_bound(g[a[i]].begin(),g[a[i]].end(),p)-g[a[i]].begin();
        if(p>=g[a[i]].size()){
          f=false;
          break;
        }
        p=g[a[i]][p];
      }
      if(f){
        ans++;
      }
    } while(next_permutation(a,a+9));
    cout<<ans<<endl;
  }
}