Cod sursa(job #2791187)

Utilizator sandifx68Fazakas Alexandru sandifx68 Data 30 octombrie 2021 10:45:25
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.92 kb
#include <iostream>
#include <fstream>
#include <cstring>

using namespace std;

ifstream f("strmatch.in");
ofstream g("strmatch.out");

char p[2000001],s[2000001];
int pref[2000001],sir[2000001],nr,rez[1005],m,n;

void formare(){
    int i=0,j=-1;pref[0]=-1;
    while(i<m){
        while(j>=0 && p[i]!=p[j]){
            j=pref[j];
        }
        i++;
        j++;
        pref[i]=j;
    }
    return;
}

void kmp(){
    int i=0,j=0;
    while(i<n){
        while(j>=0 && s[i]!=p[j])
            j=pref[j];
        i++;
        j++;
        if(j==m){
            j=pref[j];
            nr++;
            if(nr<=1000){
                rez[nr]=i-m;
            }
        }
    }
}

int main()
{
    f.getline(p,2000001);
    f.getline(s,2000001);
    m=strlen(p);n=strlen(s);
    formare();
    kmp();
    g<<nr<<"\n";
    for(int i=1;i<=(nr<=1000?nr:1000);i++)
        g<<rez[i]<<" ";

}