Cod sursa(job #3176630)

Utilizator bostanlucastefanBostan Luca-Stefan bostanlucastefan Data 27 noiembrie 2023 14:16:04
Problema Potrivirea sirurilor Scor 36
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.69 kb
#include <fstream>
#include <vector>
#define pb push_back

using namespace std;

ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

const int N=2e6+2;

vector<int> ans;
string a,b;
int nr,i,j;
int p[N];

int main()
{
    fin>>a>>b;
    for(i=1; i<a.size(); i++)
    {
        while(j && a[j]!=a[i])
            j=p[j-1];
        if(a[j]=a[i])
            j++;
        p[i]=j;
    }
    for(i=j=0; i<b.size(); i++)
    {
        while(j && a[j]!=b[i])
            j=p[j-1];
        j+=(a[j]==b[i]);
        if(j==a.size())
            ans.pb(i+1-a.size()), j=p[j-1];
    }
    fout<<ans.size()<<'\n';
    for(auto i:ans)
        fout<<i<<' ';
    return 0;
}