Cod sursa(job #2937860)

Utilizator cezarinfoTulceanu Cezar cezarinfo Data 11 noiembrie 2022 10:52:34
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.07 kb
#include<iostream>
#include<fstream>
#include<string>
#include<queue>
#include<algorithm>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
const int NMAX=2000007;
int i,len,kmp[2*NMAX],siz,spat,ct,ind;
string a,b,c;
queue<int> q;
int main()
{
    in>>a>>b;
    c.push_back('*');
    spat=a.size();
    a.append(c);
    a.append(b);
    siz=a.size();
    i=1;
    len=0;
    while(i<siz)
    {
        if(a[len]==a[i])
        {
            len++;
            kmp[i]=len;
            i++;
        }
        else
        {
            if(len==0)
            {
                kmp[i]=0;
                i++;
                continue;
            }
            if(len>0)
            {
                len=kmp[len-1];
            }
        }
    }
    for(i=spat;i<siz;i++)
    {
        if(kmp[i]==spat)
        {
            ind=i-2*spat;
            q.push(ind);
            ct++;
        }
    }
    out<<ct<<"\n";
    for(i=0;i<min(ct,1000);i++)
    {
        out<<q.front()<<" ";
        q.pop();
    }
}