Cod sursa(job #2482967)

Utilizator elenaisaiaElena Isaia elenaisaia Data 29 octombrie 2019 08:57:26
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.22 kb
#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>
#define ceva 2000003

using namespace std;

char a[ceva],b[ceva];
int n,m,pref[ceva],nr;
vector<int>sol;

void citire()
{
    a[0]=b[0]='*';
    ifstream fin("strmatch.in");
    fin>>a+1>>b+1;
    n=strlen(a+1);
    m=strlen(b+1);
}

void prefix()
{
    int p=0;
    for(int i=2;i<=n;i++)
    {
        while(p>0&&a[i]!=a[p+1])
            p=pref[p];
        if(a[i]==a[p+1])
            ++p;
        pref[i]=p;
    }
}

void kmp()
{
    int nrc=0;
    for(int i=1;i<=m;i++)
    {
        if(b[i]==a[nrc+1])
        {
            nrc++;
            if(nrc==n)
            {
                nrc=pref[n];
                sol.push_back(i-n);
                nr++;
            }
        }
        else
        {
            while(b[i]!=a[nrc+1]&&nrc>0)
                nrc=pref[nrc];
            if(b[i]==a[nrc+1])
                nrc++;
        }
    }
}

void afisare()
{
    ofstream fout("strmatch.out");
    fout<<nr<<"\n";
    if(nr>1000)
        nr=1000;
    for(int i=0;i<nr;i++)
        fout<<sol[i]<<" ";
}

int main()
{
    citire();
    prefix();
    kmp();
    afisare();
    return 0;
}