题目

传送门: ALDS1_14_B: String Search

描述

寻找字符串P在一个文本T中出现的位置, 输出所有在T中找到的P的索引, T的索引从0开始.

输入

第一行, 给出一个文本T, 在第二行, 给出一个字符串P

输出

每行输出一个在T中找到的P的下标, 以升序输出

限制条件

(1 leq length of T leq 1000000)

(1 leq length of P leq 10000)

输入由字母字符和数字组成

样例输入1

aabaaa
aa

样例输出1

0
3
4

样例输入2

xyzz
yz

样例输出2

样例输入3

abc
xyz

样例输出3

求解

分析

尝试了普通的查找, 从T开始遍历, 如果第一次匹配了, 然后将当前位置给k, 然后k遍历T, j遍历P, 如果有不同则退出, 如果全部相同则输出, 之后继续之前T的遍历
但是结果是时间超时, 完全没有更好的思路, 只能查看别人的代码
tk4114的代码
根据他的思路, 只需要用i遍历一遍T就行, 中间不需要在匹配或者不匹配时往回退一段.
根据待查找的字符串, 可能会存在一部分重复的情况, 比如说: P = aaab, 在T = aaaab中查找时, i遍历T, j遍历P, 前3个a匹配完毕, 到了第四个a的时候, 前面是b, 所以不能匹配, 但是由于之前有3个a已经匹配过了, 我们不需要将i退回到第2个a的位置, 并将j退回到第一个a的位置, 而只需要将j退回到第3个a的位置, 然后重新进行比较就可以了, 相当于在P中前两个a已经比较过了. 从而减少比较的次数

设计

还是感觉有点不理解, 直接贴代码了

编码

// 参考了用户 tk4114 的代码
#include <bits/stdc++.h>
using namespace std;

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);

	char T[1000005], P[10005];
	cin.getline(T, 1000005);
	int Tl = cin.gcount() - 1;
	cin.getline(P, 10005);
	int Pl = cin.gcount() - 1;
	if (Pl > Tl) return 0;

	int jmp[10005];
	jmp[1] = 0;
	int i = 2, j = 0;
	while (i <= Pl) {
		if (P[i - 1] == P[j]) {
			i++;
			j++;
			jmp[i - 1] = j;
		} else if (j > 0) {
			j = jmp[j];
		} else {
			jmp[i] = 0;
			i++;
		}
	}

	i = 0;
	j = 0;
	while (i < Tl) {
		if (T[i] == P[j]) {
			i++;
			j++;
			if (j == Pl) {
				cout << i - Pl << endl;
				j = jmp[j];
			}
		} else if (j > 0) {
			j = jmp[j];
		} else {
			i++;
		}
	}
}

结果

由于是几乎照搬别人的代码, 就不截图了

总结

可能几天内暂时不做其他题了, 专心研究这一块