Cod sursa(job #2201085)

Utilizator rnqftwcalina florin daniel rnqftw Data 3 mai 2018 15:46:00
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.87 kb
#include<fstream>
#include<iostream>
#include<string.h>
#define NMAX 2000001
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");

int i,len,cnt,x[1001],p[NMAX],l1,l2;
char s1[NMAX],s2[NMAX];

int main(){
    cin>>s1;
    cin>>s2;
    l1=strlen(s1+1);
    l2=strlen(s2+1);
    for(i=2;i<=l1;++i)
    {
        while(len && s1[len+1]!=s1[i])
            len=p[len];
        if(s1[len+1]==s1[i])
            ++len;
        p[i]=len;
    }

    len=0;
    for(i=1;i<=l2;++i)
    {
        while(len && s1[len+1]!=s2[i])
            len=p[len];
        if(s1[len+1]==s2[i])
            ++len;
        if(len==l1){
            ++cnt;
            if(cnt<=1000) x[cnt]=i-len;
            len=p[l1];
        }
    }
    cout<<cnt<<'\n';
    int t=min(cnt,1000);
    for(i=1;i<=t;++i)
        cout<<x[i]<<' ';
    return 0;
}