Cod sursa(job #2024597)

Utilizator Johnny07Savu Ioan-Daniel Johnny07 Data 20 septembrie 2017 21:29:25
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.12 kb
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char a[2000010],b[2000010];
int n1,n2,i,j,c[2000010], sol[1010];

void make_prefix()
{
    int i,j;
    j=0;
    c[1]=0;
    for (i=2;i<=n1;i++)
    {
    while (j && a[i]!=a[j+1]) j=c[j];
    if (a[i]==a[j+1])
    {
        c[i]=j+1;
        j++;
    }
    }
}


int main()
{
    int i,j;
    int nrsol=0;
 f.getline (a,2000010);
 n1=strlen(a);
 f.getline (b,2000010);
 n2=strlen (b);
    for (i=n1;i>=1;i--)
        a[i]=a[i-1];
    for (i=n2;i>=1;i--)
        b[i]=b[i-1];
        a[0]=' ';
        b[0]=' ';
        make_prefix();

      //  for (i=1;i<=n1;i++) cout<<c[i]<<" ";
    i=0;
    for (j=1;j<=n2;j++)
{
    while (a[i+1]!=b[j] && i)
    {
        i=c[i];
    }
    if (a[i+1]==b[j])
    {
        i++;
        if (i==n1)
        {
            i=c[i];
            nrsol++;
            if (nrsol<=1000) sol[nrsol]=j-n1;
        }
    }
}
g<<nrsol<<"\n";
nrsol=min(nrsol,1000);
for (i=1;i<=nrsol;i++) g<<sol[i]<<" ";
    return 0;
}