Cod sursa(job #2556892)

Utilizator radugheoRadu Mihai Gheorghe radugheo Data 25 februarie 2020 11:54:02
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.94 kb
#include <bits/stdc++.h>

using namespace std;

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

int i, j, n, m, cnt;
int p[2000005], sol[2005];

char a[2000005], b[2000005];

int main(){
    fin >> a + 1;
    fin >> b + 1;
    n = strlen (a + 1), m = strlen (b + 1);
    for (i=2; i<=n; i++){
        while (j > 0 && a[j+1] != a[i]){
            j = p[j];
        }
        if (a[j+1] == a[i]){
            j++;
        }
        p[i] = j;
    }
    j = 0;
    for (i=1; i<=m; i++){
        while (j > 0 && a[j+1] != b[i]){
            j = p[j];
        }
        if (a[j+1] == b[i]){
            j++;
        }
        if (j == n){
            if (cnt < 1000)
                sol[++cnt] = i - j;
            else
                break;
            j = p[j];
        }
    }
    fout << cnt << "\n";
    for (i=1; i<=cnt; i++){
        fout << sol[i] << " ";
    }
    return 0;
}
//recapitulare