Cod sursa(job #2803271)

Utilizator VladMxPMihaila Vlad VladMxP Data 19 noiembrie 2021 18:49:23
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.54 kb
#include <bits/stdc++.h>
#define MaxP 1001

using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char a[2000001],b[2000001];
int urmator[2000001],nrP;
vector<int> v;

void potrivire_naiva()
{
    /// cautam a in sirul b
    int n=strlen(a),m=strlen(b),i=0;

    int j=0;
    while(i<m)
    {
        if(a[j]!=b[i])
        {
            i-=j;
            j=0;
        }
        else j++;
        i++;
        if(j==n)
        {
            ///fout<<i-n<<" ";
            nrP++;
            if(nrP<MaxP)
                v.push_back(i-n);
            else
                return;
            i=i-n+1;
            j=0;
        }
    }
}

void kmp()
{
    /// cautam a in sirul b

    // precalcul vector urmator
    int n=strlen(a);
    urmator[0]=-1;
    int i=0,j=-1;
    while(i<n)
    {
        while(j>=0&&a[i]!=a[j])
        {
            j=urmator[j];
        }
        i++;
        j++;
        urmator[i]=j;
    }

    //
    int m=strlen(b);
    i=0;
    j=0;
    while(i<m)
    {
        while(j>=0&&b[i]!=a[j])
            j=urmator[j];
        i++;j++;
        if(j==n)
        {
            ///fout<<i-n<<" ";
            nrP++;
            if(nrP<MaxP)
                v.push_back(i-n);
            else return;
        }
    }
}

int main()
{
    fin.getline(a,sizeof(a));
    fin.getline(b,sizeof(b));
    potrivire_naiva();
    //kmp();
    fout<<v.size()<<'\n';
    for(vector<int>::iterator it=v.begin();it!=v.end();it++)
        fout<<*it<<" ";
}