Cod sursa(job #2303073)

Utilizator FunnyStockyMihnea Andreescu FunnyStocky Data 15 decembrie 2018 15:35:38
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.43 kb
#include <cstdio>
#include <iostream>

using namespace std;

const int N=2000000+5;

string pat;
string s;
int m;
int n;

int pr[N];

void build()
{
    pr[0]=0;
    int p=1,cur=0;
    while(p<m)
    {
        if(pat[p]==pat[cur])
        {
            cur++;
            pr[p]=cur;
            p++;
        }
        else
        {
            if(cur==0)
            {
                p++;
            }
            else
            {
                cur=pr[cur-1];
            }
        }
    }
}

int cnt=0;
int ans[1234];

void kmp()
{
    int i=0;
    int j=0;
    while(i<n)
    {
        if(s[i]==pat[j])
        {
            i++;
            j++;
        }
        if(j==m)
        {
            cnt++;
            if(cnt<=1000)
            {
                ans[cnt]=i-m;
            }
            j=pr[j-1];
        }
        if(i<n && s[i]!=pat[j])
        {
            if(j==0)
            {
                i++;
            }
            else
            {
                j=pr[j-1];
            }
        }
    }
}

int main()
{
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
    cin>>pat>>s;
    m=pat.size();
    n=s.size();
    build();
    kmp();
    cout<<cnt<<"\n";
    if(cnt>1000)
    {
        cnt=1000;
    }
    for(int i=1;i<=cnt;i++)
    {
        cout<<ans[i]<<" ";
    }
    cout<<"\n";
    return 0;
}