Cod sursa(job #3037801)

Utilizator OrzaSERBANSerban Orza OrzaSERBAN Data 26 martie 2023 14:37:52
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.12 kb
#include <bits/stdc++.h>

using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");

int n,m,nr;
char text[2000001],s[2000001];
int lps[2000001];
queue<int> q;
void createlps()
{
    int i=1,j=0;
    while(i<m)
    {
        if(s[i]==s[j])
        {
            lps[i]=j+1;
            i++;
            j++;
        }
        else
            if(j>0)
            j=lps[j-1];
        else
        {
            lps[i]=0;
            i++;
        }
    }
}
void kmp()
{
    n=strlen(text);
    m=strlen(s);
    createlps();
    int i=0,j=0;
    while(i<n)
    {
        if(text[i]==s[j])
        {
            i++;
            j++;
        }
        else
            if(j>0)
            j=lps[j-1];
        else
            i++;
        if(j==m)
        {
            nr++;
            if(nr<=1000)
                q.push(i-j);//i-j e indexul unde l-am gasit
            j=lps[j-1];
        }
    }
}
int main()
{
    f>>s;
    f>>text;
    kmp();
    g<<nr<<'\n';
    while(q.empty()==0)
    {
        g<<q.front()<<" ";
        q.pop();
    }
    return 0;
}