Description：

给三个字符串，求本质不同的公共子串个数。

$1\leqslant L_1,L_2,L_3\leqslant 100$

Solution：

计数最关键的还是不重不漏。

有一个显而易见的想法是 $f[i][j][k]$ 表示第一个串做到了 $i$ ，第二个 $j$ ，第三个 $k$ 有多少个，然后像 HAOI2010 最长公共子序列 那题一样统计一个个数（不需要最长），然后还要容斥。

然而这题要求本质不同，就不能这样统计，肯定还是设 $f[i][j][k]$ 表示分别到这三个位置本质不同的子串个数，按照经验最后的转移方程应该是往每一个原来的序列后面加一个字符，然后把所有能转移过来的累加起来，即 $f[i][j][k]=\sum f[i'][j'][k']+w$ ，但是由于要不重不漏，这些一定已经包含了所有的情况，但是怎样才能让他们不会计算相同的， $f[i'][j'][k']$ 中的一定已经两两不同了，就要让转移过来的两两互斥，这里的做法是枚举每个字符作为新产生的子序列的最后一个字符，这样肯定不会有重的，所以转移方程为 $f[i][j][k]=\sum_{w='a'}^{'z'}f[last[1][w]][last[2][w]][last[3][w]]+1$ ，前面那个代表原来状态的每个子序列都可以加上一个字符成为新的，后面那个 $1$ ，代表 $w$ 这个单个字符的子序列，按这个 $DP$ 就行了。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

#define MAXN 110

char c[4][MAXN];

typedef long long ll;

ll f[MAXN][MAXN][MAXN];

int l[4];

int last[4][MAXN][26];

int main()

{

	scanf("%s%s%s",c[1] + 1,c[2] + 1,c[3] + 1);

	for(int k = 1;k <= 3;++k)l[k] = strlen(c[k] + 1);

	for(int k = 1;k <= 3;++k)

	{

		for(int i = 1;i <= l[k];++i)

		{

			for(int j = 0;j < 26;++j)

				last[k][i][j] = last[k][i - 1][j];

			last[k][i][c[k][i] - 'a'] = i;

		}

	}

	for(int i = 1;i <= l[1];++i)

	{

		for(int j = 1;j <= l[2];++j)

		{

			for(int k = 1;k <= l[3];++k)

			{

				for(int w = 0;w < 26;++w)

				{

					int p1 = last[1][i][w],p2 = last[2][j][w],p3 = last[3][k][w];

					if(p1 == 0 || p2 == 0 || p3 == 0)continue;

					f[i][j][k] += f[p1 - 1][p2 - 1][p3 - 1] + 1;

				}

			}

		}

	}

	cout << f[l[1]][l[2]][l[3]] << endl;

	return 0;

}