Cod sursa(job #2337153)

Utilizator FunnyStockyMihnea Andreescu FunnyStocky Data 5 februarie 2019 22:24:07
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.88 kb
#include <iostream>
#include <cstdio>
#include <vector>

using namespace std;

const int N=1000+7;

struct presuff
{
        vector<int>kek;
        vector<int>poz;
        string pat,s;
        int i;
        int j;
        int n;
        int m;
        void build(string _pat)
        {
                pat=_pat;
                m=pat.size();
                kek.resize(m,0);
                int p=1,cur=0;
                while(p<m)
                {
                        if(pat[p]==pat[cur])
                        {
                                cur++;
                                kek[p]=cur;
                                p++;
                        }
                        else
                        {
                                if(cur==0)
                                {
                                        p++;
                                }
                                else
                                {
                                        cur=kek[cur-1];
                                }
                        }
                }
        }
        void next_step()
        {
                while(1)
                {
                        if(s[i]==pat[j])
                        {
                                i++;
                                j++;
                                if(j==m)
                                {
                                        poz.push_back(i-m);
                                        j=kek[j-1];
                                }
                                break;
                        }
                        if(s[i]!=pat[j])
                        {
                                if(j==0)
                                {
                                        i++;
                                        break;
                                }
                                else
                                {
                                        j=kek[j-1];
                                }
                        }
                }
        }
        void kmp(string _s)
        {
                poz.clear();
                s=_s;
                int n=s.size();
                i=j=0;
                while(i<n)
                {
                        next_step();
                }
        }
};

int main()
{
        freopen("strmatch.in","r",stdin);
        freopen("strmatch.out","w",stdout);
        string pat;
        cin>>pat;
        string s;
        cin>>s;
        presuff slover;
        slover.build(pat);
        slover.kmp(s);
        cout<<slover.poz.size()<<"\n";
        if(slover.poz.size()>1000)
        {
                slover.poz.resize(1000);
        }
        for(auto &it:slover.poz)
        {
                cout<<it<<" ";
        }
        cout<<"\n";
        return 0;
}