Cod sursa(job #3170504)

Utilizator tudor_bustanBustan Tudor Gabriel tudor_bustan Data 17 noiembrie 2023 18:41:48
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.93 kb
#include <iostream>
#include <fstream>
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char a[2000009], b[2000009];
int p[2000009];
vector<int> sol;
int main()
{
    fin.getline(a+1, 2000009);
    fin.getline(b+1, 2000009);
    int i=1, j=0;
    int n=strlen(a+1);
    int c=1, ok=2;
    p[0]=-1;
    while(i<=n)
    {
        while(j>0 && a[i]!=a[j])
        {
            j=p[j-1]+1;
        }
        p[i]=j;
        i++;
        j++;
    }
    int m=strlen(b+1);
    i=1;j=1;
    while(i<=m)
    {
        while(j>0 && b[i]!=a[j])
        {
            j=p[j-1]+1;
        }
        i++, j++;
        if(j==n+1)
        {
            j=p[j-1]+1;
            sol.push_back(i-n-1);
        }
    }
    int nr=sol.size();
    fout<<sol.size()<<"\n";
    for(int i=0; i<min(1000,nr); i++)
    {
        fout<<sol[i]<<" ";
    }
    return 0;
}