Cod sursa(job #2428903)

Utilizator FunnyStockyMihnea Andreescu FunnyStocky Data 6 iunie 2019 19:40:34
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.94 kb
#include <bits/stdc++.h>

using namespace std;

const int N=(int)2e6+7;
int n,m;
string pat;
string s;
int ps[N];

void uga()
{
        int i=1,cur=0;
        while(i<m)
        {
                if(pat[i]==pat[cur])
                {
                        cur++;
                        ps[i]=cur;
                        i++;
                }
                else
                {
                        if(cur==0)
                        {
                                i++;
                        }
                        else
                        {
                                cur=ps[cur-1];
                        }
                }
        }
}

int sol[1000+7],cnt;

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

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