B msc 和 mcc

题意：

对于一个字符串A，查询里面含有两个不重复子序列序列msc，mcc的子串个数

分析：

经过打表排除发现能够包含以下子序列的字符串都可以满足条件

char ch[10][100] = {"mccmsc","mcmcsc","mcmscc","mmccsc","mmcscc","mmsccc","mscmcc","msmccc"};

所以对于A的每一个位置i,找到最小的j,使得A[i,j] 包含上述子序列中的一个，这个位置的贡献是n-j+1,统计所有的贡献即可

#include<bits/stdc++.h>

using namespace std;
typedef long long LL;
const int maxn = 1e6+10;
char ar[maxn];
int  br[maxn];
int  nxt[maxn][4];
int  tmp[4];
map<char,int> ma;


char ch[10][100] = {"mccmsc","mcmcsc","mcmscc","mmccsc","mmcscc","mmsccc","mscmcc","msmccc"};
int Find(int a,int b){
   int j = 0;
   if(ar[a] == ch[b][0])
    j++;
   for(;j < 6; ++j){
    // cout<<"1"<<endl;
     int idx = ma[ch[b][j]];
     if(nxt[a][idx] != -1)
      a = nxt[a][idx];
     else
      return -1;
   }
   return a;
}
int main(){
  ma['m'] = 0;
  ma['s'] = 1;
  ma['c'] = 2;
  int n;
  cin>>n;
  cin>>(ar+1);
  for(int i = 1;i <= n; ++i)
    br[i] = ma[ar[i]];
  for(int i = 0;i < 4; ++i)
    tmp[i] = -1;
  for(int i = n;i >= 1; --i){
    for(int j = 0;j < 3; ++j)
      nxt[i][j] = tmp[j];
    tmp[br[i]] = i;
    // cout<<tmp[br[i]]<<endl;
    // cout<<i<<" "<<nxt[i][0]<<endl;
  }

  LL ans = 0;
  for(int i  = 1;i <= n; ++i){
    int Min = n+1;
    for(int j = 0;j < 8; ++j){
      int  t = Find(i,j);
      if(t != -1){
        Min = min(Min,t);
      }
    }
    if(Min == n+1)
      break;
    else
      ans += n-Min+1;
  }
  cout<<ans<<endl;



  return 0;
}

/*
mccmsc
mcmcsc
mcmscc
mcsmcc
mmccsc
mmcscc
mmsccc
mscmcc
msmccc
*/