Cod sursa(job #2338783)

Utilizator mariusn01Marius Nicoli mariusn01 Data 7 februarie 2019 20:10:49
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.88 kb
#include <fstream>
#include <cstring>

using namespace std;
char a[2000010], b[2000010];
int p[2000010];
int n, m, L, sol;
int s[1010];

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

    fin>>a+1;
    fin>>b+1;
    n = strlen(a+1);
    m = strlen(b+1);

    p[1] = 0;
    L = 0;
    for (int i=2;i<=n;i++) {
        while(L && a[i] != a[L+1])
            L = p[L];
        if (a[i] == a[L+1])
            L++;
        p[i] = L;
    }

    L = 0;
    for (int i=1;i<=m;i++) {
        while (L && b[i] != a[L+1])
            L = p[L];
        if (b[i] == a[L+1])
            L++;
        if (L == n) {
            sol++;
            if (sol <= 1000)
                s[sol] = i-n;
            L = p[L];
        }
    }
    fout<<sol<<"\n";
    for (int i=1;i<=min(sol, 1000);i++)
        fout<<s[i]<<" ";
    return 0;
}