Cod sursa(job #3195112)

Utilizator BogaBossBogdan Iurian BogaBoss Data 20 ianuarie 2024 09:45:49
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.04 kb
#include <bits/stdc++.h>

using namespace std;

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

string a,b;
int tabel[2000001];
int n,m;
queue<int>q;
int ans=0;

int main()
{
    int k=0,i=1;
    fin>>a>>b;
    n=a.size();
    m=b.size();
    while(i<n)
    {
        if(a[i]==a[k])
        {
            k++;
            tabel[i]=k;
            i++;
        }
        else if(k!=0) { k = tabel[k-1]; }
        else
        {
            tabel[i] = 0;
            i++;
        }
    }
    k=0;
    i=0;
    while(i<=m)
    {
        if(b[i]==a[k])
        {
            i++;
            k++;
            if(k==n)
            {
                ans++;
                if(ans<=1000)
                    q.push(i-n);
                k=tabel[k-1];
            }
        }
        else {
            if(k!=0)
                k=tabel[k-1];
            else i++;
        }
    }
    fout<<ans<<'\n';
    while(!q.empty())
    {
        fout<<q.front()<<" ";
        q.pop();
    }
    return 0;
}