Cod sursa(job #1967788)

Utilizator mihai.alphamihai craciun mihai.alpha Data 17 aprilie 2017 01:38:38
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.83 kb
#include <bits/stdc++.h>

using namespace std;

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

#define dim 2000000

char a[dim + 2], b[dim + 2];
int pi[dim + 2], pos[dim + 2], nrpos;

int main()  {
    f >> (a + 1) >> (b + 1);
    int m = strlen(a + 1), n = strlen(b + 1);
    int k = 0;
    for(int i = 2;i <= m;i++)  {
        while(k && a[k + 1] != a[i])
            k = pi[k];
        if(a[k + 1] == a[i])
            k++;
        pi[i] = k;
    }
    k = 0;
    for(int i = 1;i <= n;i++)  {
        while(k && a[k + 1] != b[i])
            k = pi[k];
        if(a[k + 1] == b[i])
            k++;
        if(k == m)  {
            pos[++nrpos] = i - m;
            k = pi[m];
        }
    }
    g << nrpos << "\n";
    for(int i = 1;i <= min(nrpos, 1000);i++)
        g << pos[i] << " ";
    f.close(), g.close();
    return 0;
}