Cod sursa(job #2305004)

Utilizator radugheoRadu Mihai Gheorghe radugheo Data 18 decembrie 2018 22:34:47
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.1 kb
#include <bits/stdc++.h>
#define DIM 2000005

using namespace std;

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

int n, m, i, L, k;
int p[DIM], sol[1005];

char a[DIM], b[DIM];

int main(){
    //A[i] = lungimea maxima a unui sufix terminat pe pozitia i care e in acelasi timp prefix (lungime < i).
    fin >> a + 1, n = strlen(a + 1);
    fin >> b + 1, m = strlen(b + 1);
    L = 0, p[1] = 0;
    for (i=2; i<=n; i++){
        while (a[i] != a[L+1] && L != 0){
            L = p[L];
        }
        if (a[i] == a[L+1]){
            L++;
        }
        p[i] = L;
    }
    L = 0;
    for (i=1; i<=m; i++){
        while (b[i] != a[L+1] && L != 0){
            L = p[L];
        }
        if (b[i] == a[L+1]){
            L++;
        }
        if (L == n){ /// daca gasesc potrivire
            k++;
            if (k <= 1000){
                sol[k] = i - n;
            }
            L = p[L];
        }
    }
    fout << k << "\n";
    if (k > 1000)
        k = 1000;
    for (i=1; i<=k; i++){
        fout << sol[i] << " ";
    }
    return 0;
}