Cod sursa(job #2238594)

Utilizator andrei42Oandrei42O andrei42O Data 6 septembrie 2018 15:05:41
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.79 kb
#include <bits/stdc++.h>
#define NMAX 2000005
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
string s,t;
vector <int> sol;
int q,n,m,i,pr[NMAX],cnt;
int main()
{
    f>>s>>t;
    n=s.size();
    m=t.size();
    s='#'+s;
    t='#'+t;
    for(i=2; i<=n; i++)
    {
        while(q&&s[i]!=s[q+1])
            q=pr[q];
        if(s[i]==s[q+1])
            q++;
        pr[i]=q;
    }
    q=0;
    for(i=1; i<=m; i++)
    {
        while(q&&t[i]!=s[q+1])
            q=pr[q];
        if(t[i]==s[q+1])
            q++;
        if(q==n)
        {
            q=pr[q];
            if(cnt<1000)
                sol.push_back(i-n);
            cnt++;
        }
    }
    g<<cnt<<'\n';
    for(auto it:sol)
        g<<it<<' ';

    return 0;
}