题目

传送门: 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

1

样例输入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++;
        }
    }
}

结果

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

总结

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

[Aizu] ALDS1_14_B: String Search

原文：https://www.cnblogs.com/by-sknight/p/10944961.html