Cod sursa(job #1953419)

Utilizator tudormaximTudor Maxim tudormaxim Data 4 aprilie 2017 20:17:02
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.19 kb
#include <bits/stdc++.h>
using namespace std;

ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");

const int maxn = 2e6 + 5;
int Next[maxn];

void Prefix (string Pattern, int m) {
    int x = 0, i;
    Next[0] = 0;
    for (i = 2; i <= m; i++) {
        while (x > 0 && Pattern[x + 1] != Pattern[i]) x = Next[x];
        if (Pattern[x + 1] == Pattern[i]) x++;
        Next[i] = x;
    }
}

void KMP (string Str, string Pattern, int n, int m) {
    vector <int> Ans;
    int i, x = 0;
    Prefix(Pattern, m);
    for (i = 1; i <= n; i++) {
        while (x > 0 && Pattern[x + 1] != Str[i]) x = Next[x];
        if (Pattern[x + 1] == Str[i]) x++;
        if (x == m) {
            Ans.push_back(i - m);
            x = Next[x];
        }
    }
    fout << Ans.size() << "\n";
    n = min(1000, (int) Ans.size() );
    for (i = 0; i < n; i++) {
        fout << Ans[i] << " ";
    }
    fout << "\n";
}

int main () {
    ios_base :: sync_with_stdio (false);
    string A, B;
    fin >> A >> B;
    int n = (int) B.size();
    int m = (int) A.size();
    A = "#" + A;
    B = "#" + B;
    KMP(B, A, n, m);
    fin.close();
    fout.close();
    return 0;
}