NC15334. Easygoing Single Tune Circulation
描述
Mr.Frog likes to use a music player called “NetEase Cloud Music”. There are N songs in the music library of “NetEase Cloud Music”. We use the string Si to indicate the melody of the ith song. The duration of the ith song is |Si| seconds. The phoneme of the ith song at jth second(j ∈ [1,|Si|]) is Si,j. There are 26 types of phoneme, and we use lowercase ‘a’-‘z’ to represent them. Each phoneme appears at most once in the same song.
Every day, Mr.Frog can choose exactly one song from the music library, then he will start playing this song in the single tune circulation mode.
One day, he wants to listen a special melody “fabc”. If he chooses a song “abcdef”, he will listen the melody “abcdefabcdefab... ...”. So, he can listen the special melody from 6th second to 9th second.
In the next Q days, Mr.Frog hopes to listen a special melody Mi at the ith day. Please tell him whether he can listen this melody.
输入描述
The first line contains an integer T, where T is the number of test cases. T test cases follow.
For each test case, the first line contains one integer N, where N is the number of songs in the music library of “NetEase Cloud Music”.The next N lines, the ith line contains one string Si, where Si is the melody of the ith song.
In the (N + 2)th line contains one integer Q.
The next Q lines, the ith line contains one string Mi, where Mi is the special melody that he wants tolisten at the ith day.• 1≤T,N,Q≤105.
• |Si| ≥ 1 and each phoneme appears at most once in the same song.• 1≤|Mi|≤105.• 1 ≤ ∑|Si|,∑|Mi| ≤ 105.
• Si, Mi contains only lowercase letters.
• the sum of N in all test cases doesn’t exceed 106.
• the sum of Q in all test cases doesn’t exceed 106.
• the sum of |Si| in all test cases doesn’t exceed 106.
• the sum of |Mi| in all test cases doesn’t exceed 106.
输出描述
For each test case, output one line containing “Case #x:”, where x is the test case number (startingfrom 1). The following Q lines, each line output “YES” if he can listen the special melody at the ith day.Otherwise, output “NO”.
示例1
输入:
1 4 abcd acd ad d 5 cda ddddddd dada cda acdca
输出:
Case #1: YES YES YES YES NO
C++14(g++5.4) 解法, 执行用时: 325ms, 内存消耗: 47308K, 提交时间: 2020-07-31 17:46:11
#include<bits/stdc++.h>
using namespace std;
const int N=2e6+100;
typedef long long ll;
int kmp[N];
char t[N];
void KMP(char *t) {
int lent=strlen(t+1);
for(int i=1;i<=lent;i++) kmp[i]=0;
int j=0;
for(int i=2;i<=lent;i++) {
while(j&&t[i]!=t[j+1]) j=kmp[j];
if(t[i]==t[j+1]) j++;
kmp[i]=j;
}
}
struct SAM{
char s[N];
int ch[N*2][26],len[N*2],fa[N*2],a[N],n;
int tot=1;
int endpos_size[N],c[N];
void init() {
endpos_size[1]=len[1]=fa[1]=0;
memset(ch[1],0,sizeof ch[1]);
tot=1;
}
int newnode() {
++tot;
len[tot]=fa[tot]=endpos_size[tot]=0;
memset(ch[tot],0,sizeof ch[tot]);
return tot;
}
int add(int c,int last) {
if(ch[last][c]) {
int p=last,x=ch[p][c];
if(len[p]+1==len[x]) return x;
else {
int y=newnode();
len[y]=len[p]+1;
memcpy(ch[y],ch[x],sizeof(ch[x]));
while(p&&ch[p][c]==x) ch[p][c]=y,p=fa[p];
fa[y]=fa[x];fa[x]=y;
return y;
}
}
int p=last,np=newnode();
len[np]=len[p]+1; endpos_size[np]=1;
for(;p&&!ch[p][c];p=fa[p]) ch[p][c]=np;
if(!p) fa[np]=1;
else {
int q=ch[p][c];
if(len[q]==len[p]+1) fa[np]=q;
else {
int nq=++tot;len[nq]=len[p]+1;
memcpy(ch[nq],ch[q],sizeof(ch[q]));
fa[nq]=fa[q];fa[q]=fa[np]=nq;
for(;p&&ch[p][c]==q;p=fa[p]) ch[p][c]=nq;
}
}
return np;
}
bool check(char *s) {
int pos=1;
for(int i=1;s[i];i++)
if(ch[pos][s[i]-'a']) pos=ch[pos][s[i]-'a'];
else return 0;
return 1;
}
void solve() {
init();
int m,n,len,en,rest;
cin>>n;
for(int i=1;i<=n;i++) {
int last=1;
scanf("%s",s+1);
for(int j=1;j<=4;j++)
for(int i=1;s[i];i++) last=add(s[i]-'a',last);
}
cin>>m;
while(m--) {
scanf("%s",s+1);
KMP(s);
n=strlen(s+1);
len=n-kmp[n];
en=0;
rest=n%len;
if(len*2>n) printf("%s\n",check(s)?"YES":"NO");
else {
for(int j=1;j<=2;j++) for(int i=1;i<=len;i++) t[++en]=s[i];
for(int i=n-rest+1;i<=n;i++) t[++en]=s[i]; t[++en]=0;
printf("%s\n",check(t)?"YES":"NO");
}
}
}
}sam;
int main() {
int cas;cin>>cas;
for(int i=1;i<=cas;i++)
printf("Case #%d:\n",i),sam.solve();
}
C++11(clang++ 3.9) 解法, 执行用时: 1077ms, 内存消耗: 128904K, 提交时间: 2020-10-16 13:46:29
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<map>
#include<vector>
#include<queue>
#include<iterator>
#include<unordered_set>
#define dbg(x) cout<<#x<<" = "<<x<<endl;
#define INF 0x3f3f3f3f
#define LLINF 0x3f3f3f3f3f3f3f3f
#define eps 1e-6
using namespace std;
typedef unsigned long long LL;
typedef pair<int, int> P;
const int maxn = 1000200;
const int mod = 1000000007;
struct node{
int len, link;
map<int,int> nex;
}st[maxn*2];
int tot, last, cnt, nex[maxn];
char str[maxn];
unordered_set<LL> hsh;
void init();
void getnex();
bool check1();
bool check2();
void sam(int ch);
int main()
{
int t, n, q, i, j, k, mi, len;
scanf("%d", &t);
for(int id=1;id<=t;id++)
{
init();
hsh.clear();
scanf("%d", &n);
for(j=0;j<n;j++){
scanf("%s", str);
len = strlen(str);
getnex();
mi = len, k = nex[len];
while(k>=0){
if(len%(len-k)== 0)mi = min(len-k, mi);
k = nex[k];
}
last = 0;
for(i=0;i<len;i++)sam(str[i]-'a');
for(i=0;i<len;i++)sam(str[i]-'a');
LL hs = 0, tmp = 1;
for(i=0;i<mi;i++){
hs = hs*131+str[i]-'a'+1;
tmp = tmp*131;
}
hsh.insert(hs);
for(i=0;i<mi;i++){
int x = str[i]-'a'+1;
hs = hs*131+x - tmp*x;
hsh.insert(hs);
}
}
scanf("%d", &q);
printf("Case #%d:\n", id);
while(q--)
{
scanf("%s", str);
if(check1() || check2())puts("YES");
else puts("NO");
}
}
return 0;
}
void init()
{
st[0].link = -1, st[0].len = 0;
st[0].nex.clear();
tot = 1, last = 0, cnt = 0;
}
void sam(int ch)
{
if(st[last].nex.count(ch) && st[st[last].nex[ch]].len == st[last].len+1){
last = st[last].nex[ch];
return ;
}
int cur = tot++, i, j, p;
st[cur].len = st[last].len+1;
st[cur].nex.clear();
for(p=last;p!=-1 && !st[p].nex.count(ch);p=st[p].link)
st[p].nex[ch] = cur;
if(p == -1)
st[cur].link = 0;
else{
int q = st[p].nex[ch];
if(st[p].len +1 == st[q].len)
st[cur].link = q;
else{
int clo = tot++;
st[clo] = st[q];
st[clo].len = st[p].len+1;
for(;p!=-1 && st[p].nex[ch] == q;p=st[p].link)
st[p].nex[ch] = clo;
st[q].link = st[cur].link = clo;
}
}
last = cur;
}
void getnex()
{
nex[0] = -1;
int i=0, j=-1;
while(str[i]){
if(j == -1||str[i] == str[j])
nex[++i] = ++j;
else j = nex[j];
}
}
bool check1()
{
int p = 0, len = 0, i;
for(int i=0;str[i];i++)
if(st[p].nex.count(str[i]-'a'))p = st[p].nex[str[i]-'a'];
else return false;
return true;
}
bool check2()
{
getnex();
int len = strlen(str), L = len-nex[len];
LL ans = 0;
for(int i=0;i<L;i++)
ans = ans*131+str[i]-'a'+1;
return hsh.count(ans);
}