简洁公司网站源码,泰安搜索引擎优化招聘,网站开发什么语言好,旅游时政热点新闻这又是什么神题啊。 这题一眼AC机。然后呢企鹅也是这么想的。 写完发现企鹅看错题了。然后其实建字典树就行了。 弄个v数组表示能否匹配到第i个位置。然后因为字典里的串很短#xff0c;就判一下前面L#xff08;表示字典里最长那个串的长度#xff09;个位置能否匹配#…这又是什么神题啊。 这题一眼AC机。然后呢企鹅也是这么想的。 写完发现企鹅看错题了。然后其实建字典树就行了。 弄个v数组表示能否匹配到第i个位置。然后因为字典里的串很短就判一下前面L表示字典里最长那个串的长度个位置能否匹配可以的话就把那个位置后一位到当前位置抠出来去字典树找有没有。 复杂度应该是O(m*len*L*L)蛮大的。 其实没这么可怕因为不是每个位置都可以匹配到然后匹配到一个OK就可以break了,还有只要连续L个不能匹配答案就出来了。 #includecstdio
#includeiostream
#includecstring
#includecstdlib
#includealgorithm
#includecmath
using namespace std;char ss[1100000];
struct Trie
{int c,w[30];Trie(){c0;memset(w,0,sizeof(w));}
}tr[310];int trlen;
void maketree()
{int now0,lenstrlen(ss1);for(int i1;ilen;i){int xss[i]-a1;if(tr[now].w[x]0)tr[now].w[x]trlen;nowtr[now].w[x];}tr[now].c1;
}
bool findchuan(int l,int r)
{int now0;for(int il;ir;i){int xss[i]-a1;if(tr[now].w[x]0)return false;nowtr[now].w[x];}if(tr[now].c0)return false;return true;
}bool v[1100000];
int main()
{int n,m,L0;scanf(%d%d,n,m);trlen0;for(int i1;in;i){scanf(%s,ss1);maketree();int lenstrlen(ss1);Lmax(L,len);}while(m--){scanf(%s,ss1);int lenstrlen(ss1);memset(v,false,sizeof(v));int ans0;for(int i1;ilen;i){bool bkfalse;if(iL){bktrue;v[i]findchuan(1,i);if(v[i]true)ansi;}if(v[i]true)continue;for(int jmax(1,i-L);ji;j){if(v[j]true){bktrue;v[i]findchuan(j1,i);if(v[i]true){ansi;break;}}}if(bkfalse)break;}printf(%d\n,ans);}return 0;
} 转载于:https://www.cnblogs.com/AKCqhzdy/p/8385375.html
