Cod sursa(job #1456995)

Utilizator greenadexIulia Harasim greenadex Data 2 iulie 2015 15:49:21
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.85 kb
#include <bits/stdc++.h>

using namespace std;

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

const int MAX = 2000005;
int pi[MAX], q, cnt;
char p[MAX], s[MAX];
vector <int> sol;

int main() {
    fin >> p + 1 >> s + 1;
    int l1 = strlen(p + 1), l2 = strlen(s + 1);
    for (int i = 2; i <= l1; i++) {
        while (q && p[q + 1] != p[i])
            q = pi[q];
        if (p[q + 1] == p[i])
            q++;
        pi[i] = q;
    }
    q = 0;
    for (int i = 1; i <= l2; i++) {
        while (q && p[q + 1] != s[i])
            q = pi[q];
        if (p[q + 1] == s[i])
            q++;
        if (q == l1) {
            cnt++;
            if (sol.size() < 1000)
                sol.push_back(i - l1);
        }
    }

    fout << cnt << '\n';
    for (auto it : sol)
        fout << it << ' ';

    return 0;
}