Cod sursa(job #2346908)

Utilizator mihaela.macarie01@yahoo.comMihaela Macarie [email protected] Data 18 februarie 2019 11:15:53
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1 kb
#include <iostream>
#include <fstream>
#include <cstring>

using namespace std;

ifstream x("strmatch.in");
ofstream y("strmatch.out");

int i,j,k,pi[2000005],v1,v2,nr,poz[1002];
char s1[2000005],s2[2000005];

void kmp()
{
    int i=2;
    int k=0;
    for(i=2;i<=v1;i++)
    {
        while(k && s1[k+1]!=s1[i])
            k=pi[k];
        if(s1[k+1]==s1[i])
            k++;
        pi[i]=k;
    }

}

void kmp1 (int &nr)
{
    int i=1;
    int k=0;
    for(i=1;i<=v2;i++)
    {
        while(k && s1[k+1]!=s2[i])
            k=pi[k];
        if(s1[k+1]==s2[i])
            k++;
        if(k==v1)
        {
            nr++;
            if(nr<=1000)
            {
                poz[nr]=i-k;
            }
        }
    }
}

int main()
{
    x>>s1+1;
    v1=strlen(s1+1);
    x>>s2+1;
    v2=strlen(s2+1);
    kmp();
    kmp1(nr);
    y<<nr<<'\n';
    for(i=1;i<=nr;i++)
    {
        y<<poz[i]<<" ";
    }
    x.close();
    y.close();
    return 0;
}