Cod sursa(job #2039939)

Utilizator randiboyPucani Catalin randiboy Data 15 octombrie 2017 10:18:54
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1 kb
#include <iostream>
#include <fstream>
#include <string.h>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
char a[2000001],b[2000001],c;
int n,h,S[2000001],s[2000001];
int k,f,ap;
int main()
{
    in>>a+1;
    n=strlen(a+1);
    in>>b+1;
    h=strlen(b+1);
    S[0]=-1;
    S[1]=0;
    for(int i=2;i<=n;i++)
    {
        k=i-1;
        c=a[i];
        while(S[k]!=-1 && a[S[k]+1]!=c)
            k=S[k];
           S[i]=S[k]+1;
    }
    for(int i=1;i<=h;i++)
    {
        while(f!=-1)
            if(a[f+1]==b[i])
                break;
            else
                f=S[f];
            if(f==-1)
                f=0;
            else
            {
                f++;
                if(f==n)
                {
                    ap++;
                    s[ap]=i-n;
                    f=S[f];
                }
            }
    }
    out<<ap<<"\n";
    for(int i=1;i<=min(ap,1000);i++)
        out<<s[i]<<" ";
    return 0;
}