Cod sursa(job #3170498)

Utilizator dragosdragonnIosub Dragos Casian dragosdragonn Data 17 noiembrie 2023 18:40:11
Problema Potrivirea sirurilor Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.11 kb
#include <iostream>
#include <cstring>
#include <fstream>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char sir[2000001];
char subsir[2000001];
int patern[2000001];
int cnt;
int poz[1001];
int n,m;
void citire()
{
    fin>>(subsir+1);
    fin>>(sir+1);
    m=strlen(sir+1);
    n=strlen(subsir+1);
}
void getpatern()
{
    int j = 0;
    for(int i = 2; i <= n; i++)
    {
        while(j > 0 && subsir[i] != subsir[j + 1])
        {
            j = patern[j];
        }
        if(subsir[i] == subsir[j + 1])
        {
            j++;
        }
        patern[i] = j;
    }
}
void kmp()
{
    int j=1;
    for(int i=1; i<=m; i++)
    {
        while(j>0 && subsir[j]!=sir[i])
        {
            j=patern[j-1]+1;
        }
        j++;
        if(j==n+1)
        {
            poz[cnt++]=i-j+1;
            j=patern[j-1]+1;
        }
    }
}
int main()
{
    citire();
    patern[0]=-1;
    getpatern();
    kmp();
    fout<<cnt<<'\n';
    for(int i=0; i<cnt && i<=1000; i++)
    {
        fout<<poz[i]<<" ";
    }
    return 0;
}