WA在最后一个点,求调
查看原帖
WA在最后一个点,求调
310439
星星与辰楼主2022/11/25 15:11
#include <bits/stdc++.h>
using namespace std;
inline int read()
{
    int v (0);
    char c (getchar());
    while(!isdigit(c)) c = getchar();
    while(isdigit(c)) v = (v << 1) + (v << 3) + (c & 15) , c = getchar();
    return v;
}
int nxt[10505][27] , cnt (1) , fail[10505] , id[10505] , cnt2[10505] , cnt1[10505];
void Insert (char *s , const int idd)
{
	int now (0);
	const char *ed (s + strlen(s)); 
	for (char *i (s) ; i != ed ; ++ i)
	{
		(*i) &= 31;
		if (nxt[now][*i]) now = nxt[now][*i];
		else now = nxt[now][*i] = ++ cnt;
	}
	id[now] = idd;
}
void Get_Fail ()
{
	queue<int> q;
	for (int *i (nxt[0] + 1) , *ed (nxt[0] + 27) ; i != ed ; ++ i) if (*i) q.push(*i);
	while(!q.empty())
	{
		const int x (q.front());
		q.pop();
		for (int i (1) ; i <= 26 ; ++ i)
		{
			if (nxt[x][i])
			{
				fail[nxt[x][i]] = nxt[fail[x]][i];
				q.push(nxt[x][i]);
			}else nxt[x][i] = nxt[fail[x]][i];
		}
	}
}
void Get_Ans (char *s)
{
	int now (0);
	const char *ed (s + strlen(s));
	for (char *i (s) ; i != ed ; ++ i)
	{
		now = nxt[now][(*i) & 31];
		++ cnt2[now];
	}
	for (int i (cnt) ; ~i ; -- i) cnt2[fail[i]] += cnt2[i];
	for (int i (cnt) ; ~i ; -- i)
		cnt1[id[i]] = cnt2[i];
}
char s1 [155][75];
char s [1000005];
int main() {
    int n;
    while (n = read())
    {
    	memset(nxt , 0 , sizeof (nxt));
    	cnt = 0;
    	memset(fail , 0 , sizeof (fail));
    	memset(id , 0 , sizeof (id));
    	memset(cnt2 , 0 , sizeof (cnt2));
    	for (int i (1) ; i <= n ; ++ i)
    	{
	        scanf("%s" ,  s1[i]);
	        Insert(s1[i] , i);
    	}
	    Get_Fail();
	    scanf("%s" , s);
		Get_Ans(s);
		int maxn (1) , q[155] , top (1);
		q[1] = 1;
		for (int i (2) ; i <= n ; ++ i)
		{
			if (cnt1[i] > cnt1[maxn])
				q[top = 1] = maxn = i;
			else if (cnt1[i] == cnt1[maxn])
				q[++top] = i;
		}
		printf("%d\n" , cnt1[maxn]);
		for (int i (1) ; i <= top ; ++ i)
		{
			for (char *c (s1[q[i]]) , *ed (s1[q[i]] + strlen(s1[q[i]])) ; c != ed ; ++ c)
				putchar((*c) | 96);
			puts("");
		}
    }
    return 0;
}
2022/11/25 15:11
加载中...