Cod sursa(job #2084280)

Utilizator vladschillerVlad Radu Schiller vladschiller Data 8 decembrie 2017 21:27:05
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 1 kb
#include <iostream>
#include <fstream>
#include <cstring>
#define nmax 2000005
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char a[nmax],b[nmax];
int l[nmax],out[1005];
int main()
{
    int i,j,nr=0,var=0;
    f.getline(a,nmax);
    f.get();
    f.getline(b,nmax);
    l[0]=0;
    i=1;
    j=0;
    int lena=strlen(a),lenb=strlen(b);
    while(i<lena)
        if(a[i]==a[j])
        {
            l[i]=j+1;
            i++;
            j++;
        }
        else if(j==0)
            l[i++]=0;
        else
            j=l[j-1];
    i=0;
    j=0;
    while(i<lenb)
        if(b[i]==a[j])
        {
            i++,j++;
            if(j==lena)
            {
                nr++;
                j=l[j-1];
                if(nr<=1000)
                    out[var++]=i-lena;
            }
        }
    else if(j==0)
        i++;
    else
        j=l[j-1];
    g<<nr<<'\n';
    for(int i=0;i<var;++i)
        g<<out[i]<<' ';
    return 0;
}