序列自动机（模板）

题目：Summer Trip

#include<bits/stdc++.h>
using namespace std;
#define ll long long
string s;
vector<int>ve[30];  //v[i][j]表示记录序列中第j个i字母的位置
ll fun(int a,int b){
	ll res=0;
	int lena=ve[a].size();
	int lenb=ve[b].size();
	int j=0;
	for(int i=0;i<lena;i++){
		while(j<lenb && ve[b][j]<ve[a][i] ) j++;  //这里的判断条件不能反过来，否则会访问非法内存
		if(j==lenb) break;
		if(ve[a][i+1]>ve[b][j] || i+1==lena) res++;
	}
	return res;	
}
int main(){
	cin >> s;
	int len=s.size();
	for(int i=0;i<len;++i){
		ve[ s[i]-'a' ].push_back(i);
	}
	ll ans=0;
	for(int i=0;i<26;++i){
		for(int j=0;j<26;++j){
			if(i==j) continue;
			ans+=fun(i,j);
		}
	}
	cout << ans ;
	return 0;
}