[TJOI2008] 公共子串 https://www.luogu.org/problemnew/show/P3856
f[i][j][k] 表示 a 数组前 i 个值 b 数组前 j 个值 c 数组前 k 个值中的本质不同的公共字串有多少个
N3 每次都重新计算
- #include<bits/stdc++.h>
- using namespace std;
- #define rg register
- const int N=100+5,inf=0x3f3f3f3f;
- int n=0,la,lb,lc;
- char a[N],b[N],c[N];
- long long las[4]['z'+5],f[N][N][N];
- template<class t>void rd(t &x)
- {
- x=0;int w=0;char ch=0;
- while(!isdigit(ch)) w|=ch=='-',ch=getchar();
- while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
- x=w?-x:x;
- }
- int main()
- {
- // freopen("in.txt","r",stdin);
- scanf("%s%s%s",a,b,c);
- la=strlen(a),lb=strlen(b),lc=strlen(c);
- for(rg int i=0;i<la;++i)
- {
- las[1][a[i]]=i+1;memset(las[2],0,sizeof(las[2]));
- for(rg int j=0;j<lb;++j)
- {
- las[2][b[j]]=j+1;memset(las[3],0,sizeof(las[3]));
- for(rg int k=0;k<lc;++k)
- {
- las[3][c[k]]=k+1;
- for(rg int x='a';x<='z';++x)
- {
- int aa=las[1][x],bb=las[2][x],cc=las[3][x];
- if(!aa||!bb||!cc) continue;
- f[i+1][j+1][k+1]+=f[aa-1][bb-1][cc-1]+1;
- }
- }
- }
- }
- printf("%lld",f[la][lb][lc]);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3045454.html