Cod sursa(job #3195103)

Utilizator IleaIlea Bogdan Ilea Data 20 ianuarie 2024 09:42:26
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.08 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin;
ofstream fout;

char a[2000005], b[2000005];
int tabel[2000005], n, m, k, i, cont=0;
vector<int> v;

int main()
{
    fin.open("strmatch.in");
    fin>>a>>b;
    fin.close();
    n=strlen(a), m=strlen(b);
    i=1;
    while (i<n){
        if (a[i]==a[k]){
            k++;
            tabel[i]=k;
            i++;
        }
        else if (k!=0){
            k=tabel[k-1];
        }
        else {
            tabel[i]=0;
            i++;
        }
    }
    i=0, k=0;
    while (i<m){
        if (b[i]==a[k]){
            i++;
            k++;
            if (k==n){
                cont++;
                if (cont<=1000){
                    v.push_back(i-n);
                }
                k=tabel[k-1];
            }
        }
        else if (b[i]!=a[k]){
            if (k!=0)k=tabel[k-1];
            else i++;
        }
    }
    fout.open("strmatch.out");
    fout<<cont<<endl;
    for (i=0; i<v.size(); i++){
        fout<<v[i]<<" ";
    }
    fout.close();
    return 0;
}