Cod sursa(job #1953404)

Utilizator tudormaximTudor Maxim tudormaxim Data 4 aprilie 2017 20:04:46
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.15 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 = -1, i;
    Next[0] = 0;
    for (i = 1; 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) {
    vector <int> Ans;
    int n = (int) Str.size();
    int m = (int) Pattern.size();
    int i, x = -1;
    Prefix(Pattern, m);
    for (i = 0; i < n; i++) {
        while (x > 0 && Pattern[x + 1] != Str[i]) x = Next[x];
        if (Pattern[x + 1] == Str[i]) x++;
        if (x == m - 1) {
            Ans.push_back(i - m + 1);
            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;
    KMP(B, A);
    fin.close();
    fout.close();
    return 0;
}