Cod sursa(job #1649537)

Utilizator andreimdvMoldovan Andrei andreimdv Data 11 martie 2016 14:03:40
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.9 kb
#include <fstream>
#include<vector>
#include<cstring>
using namespace std;

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

char s[2000010],t[2000010];
int pi[2000010];
int k,q,i,slen,tlen,sol;
vector<int> vsol;


int main()
{
    fin>>(t+1)>>(s+1);
    slen=strlen(s+1);
    tlen=strlen(t+1);

    /// creeare pi
    for(i=2;i<=tlen;++i)
    {
        while(k>0&&t[k+1]!=t[i])
            k=pi[k];
        if(t[k+1]==t[i])
            k++;
        pi[i]=k;
    }

    for(i=1;i<=slen;++i)
    {
        while(q>0&&t[q+1]!=s[i])
            q=pi[q];
        if(t[q+1]==s[i])
            q++;
        if(q==tlen)
        {
            sol++;
            if(sol<=1000)
            {
                vsol.push_back(i-tlen);
            }
        }
    }
    fout<<sol<<'\n';
    for(i=0;i<(int)vsol.size();++i)
        fout<<vsol[i]<<" ";


    return 0;
}