Cod sursa(job #2270030)

Utilizator marian013Giugioiu Marian Constantin marian013 Data 26 octombrie 2018 23:28:36
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.97 kb
#include<fstream>
#include<string.h>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
int n,m,e;
char a[2000005],b[2000005];
int pi[2000005],v[1002];
void prefix(){
    int k=0, i;
    pi[1]=0;
    for(int i=2;i<=n;i++)
    {
        while(k>0&&a[k+1]!=a[i])
            k=pi[k];
        if(a[k+1]==a[i])
            ++k;
        pi[i]=k;
    }
}
void potrivire(){
    int k=0, i;
    prefix();
    for(int i=1;i<=m;i++)
    {
        while(k>0&&a[k+1]!=b[i])
            k=pi[k];
        if(a[k+1]==b[i])
            ++k;
        if(k==n)
        {
            k=pi[k];
            if(e<1000)
               v[++e]=i-n;
        }
    }

}
int main()
{
    int i;
    f>>a>>b;
    m=strlen(b);
    n=strlen(a);
    for(i=n;i;i--)
        a[i]=a[i-1];
        a[0]=' ';
    for(i=m;i;i--)
        b[i]=b[i-1];
        b[0]=' ';
    potrivire();
    g<<e<<"\n";
    for(i=1;i<=e;i++)
        g<<v[i]<<" ";

}