Cod sursa(job #2211443)

Utilizator AndreiVisoiuAndrei Visoiu AndreiVisoiu Data 10 iunie 2018 12:34:14
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.82 kb
#include <bits/stdc++.h>

using namespace std;

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

const int LMAX = 2000001;
char a[LMAX], b[LMAX];
int n, m, u[LMAX], pot[LMAX], nrp;

void urm() {
    int k = -1, x;
    u[0] = 0;
    for(x = 1; x < n; x++) {
        while(k > 0 && a[k+1] != a[x]) k = u[k];
        if(a[k+1] == a[x]) k++;
        u[x] = k;
    }
}

int main()
{
    in >> a >> b;
    n = strlen(a);
    m = strlen(b);
    int x = -1;

    urm();

    for(int i = 0; i < m; i++) {
        while(x > 0 && a[x+1] != b[i]) x = u[x];
        if(a[x+1] == b[i]) x++;
        if(x == n-1) {
            pot[++nrp] = i-n+1;
            x = u[x];
        }
    }
    out << nrp << '\n';
    for(int i = 1; i <= nrp && i <= 1000; i++)
        out << pot[i] << ' ';
    return 0;
}