Cod sursa(job #2288903)

Utilizator cicero23catalin viorel cicero23 Data 24 noiembrie 2018 09:15:13
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.83 kb
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char s[2000002],q[2000002];
int p[2000003],v[1001];
int main()
{
    f.getline(s+1,2000002);
    f.getline(q+1,2000002);
    int n=strlen(s+1),nr=0,i,t=0;
    int m=strlen(q+1);
    int k=0;
    if(m<n) g<<0;
    else {
    for(i=2;i<=n;i++)
    {
        while(k!=0&&s[k+1]!=s[i]) k=p[k];
        if(s[k+1]==s[i])k++;
        p[i]=k;
    }

    k=0;
    for(i=1;i<=m;i++)
        {
            while(k!=0&&s[k+1]!=q[i]) k=p[k];
            if(s[k+1]==q[i]) k++;
            if(k==n)
            {
                nr++;

                if(nr<1001) {v[nr]=i-n;t=nr;}
            }
        }
    g<<nr<<'\n';
    for(i=1;i<=t;i++)
        g<<v[i]<<" ";
    }
    return 0;
}