Cod sursa(job #2722487)

Utilizator DragosGavrusDragos Gavrus DragosGavrus Data 12 martie 2021 21:31:52
Problema Potrivirea sirurilor Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.19 kb
#include <bits/stdc++.h>

using namespace std;

int lps[1000],ap[1003],ans;

void formare_lps(char pattern[])
{
    int index=0;
    for(int i=1;i<strlen(pattern);)
    {
        if(pattern[index]==pattern[i])
        {
            lps[i]=index+1;
            index++;
            i++;
        }
        else if(index!=0)
            index=lps[index-1];
        else
        {
            lps[i]=0;
            i++;
        }
    }
}

bool KMP (char text[],char pattern[])
{
    int i=0,j=0;
    while(i<strlen(text))
    {
        if(text[i]==pattern[j])
        {
            i++;
            j++;
        }
        else if(j!=0)
        {
            j=lps[j-1];
        }
            else
            {
                i++;
            }

        if(j==strlen(pattern))
        {
            ans++;
            if(ans<=1000)
                ap[ans]=i-strlen(pattern);
        }
    }
}


char text[1000],pattern[1000];

int main()
{
    cin.getline(pattern,1000);
    cin.getline(text,1000);
    formare_lps(pattern);
    KMP(text,pattern);
    cout<<ans<<"\n";
    for(int i=1;i<=min(ans,1000);i++)
        cout<<ap[i]<<" ";
    return 0;
}