import java.util.Scanner;
public class Main {
public static void main(String[] arg) {
Scanner scanner = new Scanner(System.in);
// todo
}
}
NC25831. y大的字符串
描述
在老师小s布置的的作业题上有一道题“Search”的描述是这样的：
输入n，m,
下面给n个长度小于10的字符串
再给m个大小小于1M的文本 如果文本串的一个前缀能被那n个长度小于10的字
符串拼凑出来(n个长度小于10的字符串每个都允许使用多次)，则称这个文本串的那个前缀是能被解释的，
若有串ab,那abab的前缀有a,ab,aba,abab，其中a不能被ab解释，ab可以被自己解释，aba不行，abab可以被ab解释
求 能被解释的 最长的前缀 的长度 和 在能被解释的 最长的前缀的长度 中最长的回文串的长度。
y大看了一眼，认为十分简单，在1000ms内就秒掉了这道题，然后便去颓《splay》了，而蒟蒻的水宝宝却做不出这道题，便求助于你。
输入描述
第一行n，m 后n行为长度小于10的字符串
再后m行，m个大小小于1M的文本
输出描述
m行,每行对应一个询问 需要输出两个整数,第一个数代表 能被解释的 最长的前缀 的长度。第二个数代表在能被解释的 最长的前缀的长度 中最长的回文串的长度,具体见样例解释
示例1
输入:
4 3 ab abb abba abc abababab abbbbba ccccccc
输出:
8 7 3 2 0 0
说明:
abababab都可以被解释，最长回文串是abababa，故输出8和7C++14(g++5.4) 解法, 执行用时: 60ms, 内存消耗: 20300K, 提交时间: 2019-07-01 09:26:44
#include<iostream>#include<stdio.h>#include<string.h>#include<algorithm>using namespace std;const int maxn = 1e7+5;char ss[maxn],snew[maxn*2];int nxt[maxn][30];int endd[maxn],p[maxn*2];int tot=1;void insert(char *s){int len =strlen(s);int u = 0;for(int i=0;i<len;i++){int id = s[i];if(nxt[u][id]==0)nxt[u][id] = ++tot;u = nxt[u][id];}endd[u] =1;}int query(char *ss,int len){int u=0,res = 0;for(int i=0;i<len;i++){int t = nxt[u][ss[i]];u =t;if(endd[u]){res = i+1;if(i+1==len)break;if(nxt[t][ss[i+1]]==0)u=0;}if(t==0)break;}return res;}int init(int len){int j=2;snew[0]='$',snew[1]='#';for(int i=0;i<len;i++){snew[j++]=ss[i];snew[j++] = '#';}snew[j] = '\0';return j;}int Man(int len) {int len_max = -1,mx=0,id;for(int i=1;i<len;i++){p[i] = mx>i ?min(p[id*2-i],mx-1) :1 ;while(snew[p[i]+i]==snew[i-p[i]])p[i]++;if(p[i]+i>mx){id = i;mx = p[i] + i;}len_max= max(len_max,p[i]-1);}return len_max;}int main(){int n,m;scanf("%d%d",&n,&m);for(int i=1;i<=n;i++){scanf("%s",ss);insert(ss);}while(m--){scanf("%s",ss);int s1 = query(ss,strlen(ss));int s2 = Man(init(s1));cout<<s1<<" "<<s2<<endl;}}
C++11(clang++ 3.9) 解法, 执行用时: 44ms, 内存消耗: 10340K, 提交时间: 2020-03-18 13:03:18
#include<iostream>#include<stdio.h>#include<string.h>#include<algorithm>using namespace std;const int maxn=1e7+5;char ss[maxn],snew[maxn*2];int nxt[maxn][30];int endd[maxn],p[maxn*2];int tot=1;void insert(char *s){int len=strlen(s);int u=0;for(int i=0;i<len;i++){int id=s[i];if(nxt[u][id]==0) nxt[u][id]=++tot;u=nxt[u][id];}endd[u]=1;}int query(char *ss,int len){int u=0,res=0;for(int i=0;i<len;i++){int t=nxt[u][ss[i]];u=t;if(endd[u]){res=i+1;if(i+1==len) break;if(nxt[t][ss[i+1]]==0) u=0;}if(t==0) break;}return res;}int init(int len){int j=2;snew[0]='$',snew[1]='#';for(int i=0;i<len;i++){snew[j++]=ss[i];snew[j++]='#';}snew[j]='\0';return j;}int Man(int len){int len_max=-1,mx=0,id;for(int i=1;i<len;i++){p[i]=mx>i?min(p[id*2-i],mx-1):1;while(snew[p[i]+i]==snew[i-p[i]])p[i]++;if(p[i]+i>mx){id=i;mx=p[i]+i;}len_max=max(len_max,p[i]-1);}return len_max;}int main(){int n,m;scanf("%d%d",&n,&m);for(int i=1;i<=n;i++){scanf("%s",ss);insert(ss);}while(m--){scanf("%s",ss);int s1=query(ss,strlen(ss));int s2=Man(init(s1));cout<<s1<<" "<<s2<<endl;}}