求能被理解的最长前缀。
很显然的dp。令dp[i]=true,表示前缀i能理解。否则不能理解。那么dp[i+len]=dp[i]=true,当s[len]能匹配str[i,i+len].
由于模式串长度为10.且匹配过程可以用字典树加速。
所以复杂度就是O(10*m*len).
# include <cstdio> # include <cstring> # include <cstdlib> # include <iostream> # include <vector> # include <queue> # include <stack> # include <map> # include <set> # include <cmath> # include <algorithm> using namespace std; # define lowbit(x) ((x)&(-x)) # define pi acos(-1.0) # define eps 1e-9 # define MOD 1000000000 # define INF 1000000000 # define mem(a,b) memset(a,b,sizeof(a)) # define FOR(i,a,n) for(int i=a; i<=n; ++i) # define FO(i,a,n) for(int i=a; i<n; ++i) # define bug puts("H"); # define lch p<<1,l,mid # define rch p<<1|1,mid+1,r # define mp make_pair # define pb push_back typedef pair<int,int> PII; typedef vector<int> VI; # pragma comment(linker, "/STACK:1024000000,1024000000") typedef long long LL; int Scan() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } void Out(int a) { if(a<0) {putchar('-'); a=-a;} if(a>=10) Out(a/10); putchar(a%10+'0'); } const int N=1000005; //Code begin... int trie[205][27], top; char str[N], s[15]; bool vis[N]; void init(){top=1; mem(trie[0],0);} void ins(char *s){ int rt, nxt; for (rt=0; *s; rt=nxt, ++s){ nxt=trie[rt][*s-'a']; if (!nxt) mem(trie[top],0), trie[rt][*s-'a']=nxt=top++; } trie[rt][26]=1; } void find(int l, int r){ int rt, nxt, i; for (rt=0, i=l; i<=r; rt=nxt, ++i) { nxt=trie[rt][str[i]-'a']; if (!nxt) return ; if (trie[nxt][26]) vis[i]=true; } } int main () { int n, m; scanf("%d%d",&n,&m); init(); FOR(i,1,n) scanf("%s",s+1), ins(s+1); FOR(i,1,m) { scanf("%s",str+1); int len=strlen(str+1); mem(vis,0); vis[0]=true; int ans; FOR(j,0,len) if (vis[j]) find(j+1>len?len:j+1,j+10>len?len:j+10), ans=j; printf("%d ",ans); } return 0; }