Description：

有两行石头，每个石头都是 $RGB$ 其中之一，依次报出一个 $RGB$ 序列，有两个人开始时站在第一个石头上，如果听到的和自己脚下的一样，就前进一步，问不同的序列最终两个人的位置有多少种可能。

$1\leqslant n\leqslant 10^6$

Solution：

看数据范围需要一个 $O(n)$ 做法，不难想到对于第一个序列的每个位置，第二个序列合法的位置是一个左右端点单调的区间，所以可以用双指针，右端点能移就移，左端点不得不移时才移，但是打一个表会发现区间不是连续的，事实上当 $A=\cdots xy,B=\cdots yx$ 时是不可能的，所以记 $sum[p][i][j]$ 表示前 $p$ 位，最后一位是 $j$ ，倒数第二位是 $i$ 的个数，这个其实是一个前缀和，这样就能统计这种情况了。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

#define MAXN 1000010

char s[MAXN],t[MAXN];

int ls,lt;

int sum[MAXN][3][3];

int main()

{

	scanf("%s%s",s + 1,t + 1);

	ls = strlen(s + 1);lt = strlen(t + 1);

	if(ls > lt){swap(ls,lt);swap(s,t);}

	for(int i = 1;i <= ls;++i)

	{

		if(s[i] == 'R')s[i] = 0;

		if(s[i] == 'G')s[i] = 1;

		if(s[i] == 'B')s[i] = 2;

	}

	for(int i = 1;i <= lt;++i)

	{

		if(t[i] == 'R')t[i] = 0;

		if(t[i] == 'G')t[i] = 1;

		if(t[i] == 'B')t[i] = 2;

	}

	long long ans = 0;

	int l = 1,r = 1;

	while(r < lt && t[r] != s[1])

	{

		++r;

		for(int j1 = 0;j1 < 3;++j1)

			for(int j2 = 0;j2 < 3;++j2)

				sum[r][j1][j2] = sum[r - 1][j1][j2];

		++sum[r][t[r - 1]][t[r]];

	}

	for(int i = 1;i <= ls;++i)

	{

		while(r < lt && t[r] != s[i])

		{

			++r;

			for(int j1 = 0;j1 < 3;++j1)

				for(int j2 = 0;j2 < 3;++j2)

					sum[r][j1][j2] = sum[r - 1][j1][j2];

			++sum[r][t[r - 1]][t[r]];

		}

		ans += r - l + 1;

		if(s[i] != s[i - 1])ans -= sum[r][s[i]][s[i - 1]] - sum[l - 1][s[i]][s[i - 1]];

		if(s[i] == t[l])++l;

		if(r < lt)

		{

			++r;

			for(int j1 = 0;j1 < 3;++j1)

				for(int j2 = 0;j2 < 3;++j2)

					sum[r][j1][j2] = sum[r - 1][j1][j2];

			++sum[r][t[r - 1]][t[r]];

		}

	}

	cout << ans << endl;

	return 0;

}