Cod sursa(job #1774112)

Utilizator BlackLordFMI Alex Oprea BlackLord Data 8 octombrie 2016 16:19:24
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.97 kb
#include <fstream>
#include <cstring>

using namespace std;

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

const int N=2000010;

int lena, lenb, i, j, p[N], rez[N], nr, x;
char a[N], b[N];

int main() {
    fin >> a + 1;
    fin >> b + 1;
    lena = strlen(a + 1);
    lenb = strlen(b + 1);
    p[1] = 0;
    for (i = 2; i <= lena; ++i) {
        x = p[i - 1];
        while (a[i] != a[x + 1] && x != 0)
            x = p[x];
        if (a[i] == a[x + 1]) {
            p[i] = x + 1;
        } else {
            p[i] = 0;
        }
    }
    x = 0;
    for (i = 1; i <= lenb; ++i) {
        while (b[i] != a[x + 1] && x!=0)
            x = p[x];
        if (b[i] == a[x + 1]) {
            x++;
        }
        if (x == lena) {
            rez[++nr] = i - lena;
            x = p[x];
        }
    }
    fout << nr << "\n";
    for (i = 1; i <= nr; ++i) {
        fout << rez[i] << ' ';
    }
    fout << "\n";
    return 0;
}