【题解】[JSOI2012]玄武密码

题目链接

  • 你谷：P5231[JSOI2012]玄武密码
  • LOJ: #10058. 「一本通 2.4 练习 1」玄武密码

题意

输出模式串在文本串中能够匹配上的最长前缀。

输入格式

第一行有两个整数，\(N\)和\(M\)，分别表示母串的长度和文字段的个数；

第二行是一个长度为\(N\)的字符串，所有字符都满足是 E，S，W 和 N 中的一个；

之后\(M\)行，每行有一个字符串，描述了一段带有玄武密码的文字。依然满足，所有字符都满足是 E，S，W 和 N 中的一个。

输出格式

输出有\(M\)行，对应\(M\)段文字。

每一行输出一个数，表示这一段文字的前缀与母串的最大匹配串长度。

思路

这是一道披上辣椒衣的AC自动机模板题。难点就在这层辣椒衣。

解决方法：先打标记，最后遍历。

代码实现

#include
#include
#include
#include
using namespace std;
const int N=1e5+5;
int n,m;
int t[N*100][5],cnt,fail[N*100];
char s[N][105],txt[N*100];
bool vis[N*100];
map  mp; 

inline int ans(int x){
	int p=0,ret=0;
	int l=strlen(s[x]);
	for(int i=0;i q;
	for(int i=0; i<4; i++) {
		if(t[0][i]) q.push(t[0][i]);
	}
	while(!q.empty()) {
		int p=q.front();
		q.pop();
		for(int i=0; i<4; i++) {
			if(t[p][i]) {
				q.push(t[p][i]);
				fail[t[p][i]]=t[fail[p]][i];
			} else t[p][i]=t[fail[p]][i];
		}
	}
}

inline void ins(char x[]) {
	int l=strlen(x);
	int p=0;
	for(int i=0; i

PS. 为了体验不能用万能头的感觉，没有用万能头。

反思：
必须承认，看了题解才写出看上去能算优美的代码。
一开始想要直接把trie的节点弄成包罗万象的大结点，就是说，把每个结点弄成大struct，用每个结点映射它对应的模式串，包括记录它的深度,etc。然后发现写起来很头大。
看了一篇题解，发现可以通过先打标记，最后遍历的方法来确定能匹配的前缀长度。
这是一种存储数据解题（离线）的思维。
事实上，题目提示得很明显：先输入文本串，后输入模式串。这和一般AC自动机输入数据的顺序不同，或许提示着一种更自由地对待模式串的方式（指最后遍历一遍）。

题解字符串

相关

洛谷P5340 大中锋的游乐场 题解 分层图最短路

Ubuntu 断网问题解决

js 正则匹配 两个字符串之间，某个字符串之前（之后）的内容

[SQL] SQL Server 2019 中LocalDB 报错的问题解决

大爽Python入门教程 1-2 数与字符串

Java21-统计字符串中每个字符出现的次数

全（十五）Jmeter 之 参数化 函数助手：__Random string（译：瑞德.丝锥）：随机字符串

题解 Count on a tree II/【模板】树分块

生成随机字符串

09练习：统计输入的字符串中各种字符的个数

2-14str1转义字符，格式化_2-15str2格式化，字符串内置函数

HttpURLConnection发送中文乱码问题解决

标签