题目描述

数据范围

=w=

暴力： 从前往后枚举一个i，再从前往后枚举一个j： 如果s[i]不是s[j]的子串，更新答案，继续枚举； 如果s[i]是s[j]的子串，停止枚举。 因为对于s[k] (k>j)，s[i]如果不是s[k]的子串，那么s[j]也不是s[k]的子串。

代码

#include<iostream> #include<stdio.h> #include<string.h> #include<algorithm> #include<math.h> #define ll long long using namespace std; const char* fin="sub.in"; const char* fout="sub.out"; const int inf=0x7fffffff; const int maxn=507,maxlen=2007; int t,n,i,j,k,p,ans; char s[maxn][maxlen]; int len[maxn],fail[maxn][maxlen]; bool judge(int a,int b){ int i,j,k,p=0; for (i=1;i<=len[b];i++){ while (p && s[a][p+1]!=s[b][i]) p=fail[a][p]; if (s[a][p+1]==s[b][i]) p++; if (p==len[a]) return true; } return false; } int main(){ freopen(fin,"r",stdin); freopen(fout,"w",stdout); scanf("%d",&t); while (t--){ scanf("%d",&n); for (i=1;i<=n;i++) scanf("%s",s[i]+1); for (i=1;i<=n;i++){ len[i]=strlen(s[i]+1); p=0; for (j=2;j<=len[i];j++){ while (p && s[i][p+1]!=s[i][j]) p=fail[i][p]; if (s[i][p+1]==s[i][j]) p++; fail[i][j]=p; } } ans=0; for (i=1;i<=n;i++){ for (j=max(ans,i+1);j<=n;j++) if (judge(i,j)) break; else ans=j; } if (ans) printf("%d\n",ans); else printf("-1\n"); } return 0; }

=o=

我的暴力和正解的区别： 正解：枚举i，然后处理所有i对其他人的贡献①； 我：枚举i，然后处理所有其他人对i的贡献②。 两种都显然正确； 但是区别是有的，前者可能会更容易优化。

---

类比动态规划： 对于两个等价的方程： f[1..i−1]⇒f[i] ，以及 f[i−1]⇒f[i] 。 显然后者更容易优化，栗子。

---

这个由于算的顺序不同导致我走远的栗子不唯一。 这道题当时我算的方式跟正解不同，然后我化简化得很困难。

---

以后大概两种搜索方式都尝试一下吧。