Cod sursa(job #1938861)

Utilizator NicolaalexandraNicola Alexandra Mihaela Nicolaalexandra Data 25 martie 2017 11:55:09
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.87 kb
#include <fstream>
#include <cstring>
using namespace std;
int n,m,i,l,sol,p[2000001],v[1001];
char a[2000001],b[2000001];
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");

int main (){

    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 (l!=0 && a[i] != a[l+1])
            l = p[l];
        if (a[i] == a[l+1])
            l++;
        p[i] = l;
    }
    l = 0;
    for (i=1;i<=m;i++){
        while (l!=0 && b[i] != a[l+1])
            l = p[l];
        if (b[i] == a[l+1])
            l++;
        if(l == n){
            sol ++;
            if (sol <= 1000)
                v[sol] = i-n;
            l = p[l];
        }
    }
    fout<<sol<<"\n";
    sol = min (sol, 1000);
    for (i=1;i<=sol;i++)
        fout<<v[i]<<" ";



    return 0;
}