Cod sursa(job #2260031)

Utilizator NewGloryMihnea Andreescu NewGlory Data 14 octombrie 2018 12:13:42
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.33 kb
#include <fstream>
#include <vector>

using namespace std;

ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

const int N=2000000+5;

string p,s;
int m,n;

int ps[N];

inline void build_ps()
{
    int len=0,i=1;
    ps[0]=0;
    while(i<m)
    {
        if(p[i]==p[len])
        {
            len++;
            ps[i]=len;
            i++;
        }
        else
        {
            if(len==0)
            {
                ps[i]=0;
                i++;
            }
            else
            {
                len=ps[len-1];
            }
        }
    }
}

vector<int>ans;

inline void roflan()
{
    int i=0;
    int j=0;
    while(i<n)
    {
        if(p[j]==s[i])
        {
            i++;
            j++;
        }
        if(j==m)
        {
            ans.push_back(i-j);
            j=ps[j-1];
        }
        else
        {
            if(i<n && p[j]!=s[i])
            {
                if(j!=0)
                    j=ps[j-1];
                else
                    i++;
            }
        }
    }
}

int main()
{
    fin>>p>>s;
    m=p.size();
    n=s.size();
    build_ps();
    roflan();
    fout<<ans.size()<<"\n";
    int sz=min((int)ans.size(),1000);
    for(int i=0;i<sz;i++)
        fout<<ans[i]<<" ";
    fout<<"\n";
    return 0;
}