Cod sursa(job #1910387)

Utilizator Emil64Emil Centiu Emil64 Data 7 martie 2017 16:41:08
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.83 kb
#include <bits/stdc++.h>

using namespace std;

int pi[2000001], sol[1<<10], l = 0;
char a[2000001], b[2000001];

int main()
{
    ifstream f("strmatch.in");
    ofstream g("strmatch.out");
    int n, m;
    f >> (a+1) >> (b+1);
    int i, k = 0;
    n = strlen(a+1);
    m = strlen(b+1);
    pi[1] = 0;
    for(i=2; i<=n; i++){
        while(k && a[k+1] != a[i])
            k = pi[k];
        if(a[k+1] == a[i])
            k++;
        pi[i] = k;
    }
    k = 0;
    for(i=1; i<=m; i++){
        while(k && a[k+1] != b[i])
            k = pi[k];
        if(a[k+1] == b[i])
            k++;
        if(k == n){
            k = pi[n];
            ++l;
            if(l<=1000){
                sol[l] = i-n;
            }
        }
    }
    g << l << "\n";
    l = min(l, 1000);
    for(i=1; i<=l; i++)
        g << sol[i] << " ";
    g << "\n";
}