Cod sursa(job #2024578)

Utilizator Johnny07Savu Ioan-Daniel Johnny07 Data 20 septembrie 2017 20:58:03
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 0.74 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];
int main()
{
    int nrsol=0;
 f.getline (a,2000010);
 n1=strlen(a)-1;
 f.getline (b,2000010);
 n2=strlen (b) -1;
int i;
j=0;
//cout<<n1;
for (i=1;i<=n1;i++)
{
    if (a[i]!=a[j]) j=0;
    if (a[i]==a[j]) {c[i]=j+1;j++;}
}
//for (i=0;i<=n1;i++) cout << c[i]<< " ";

i=0;
for (j=0;j<=n2;j++)
{
while (i && a[i]!=b[j])
    i=c[i];
if (a[i]==b[j]) i++;
if (i==n1)
{
    nrsol++;
    i=c[i];
    if (nrsol<1000) sol[nrsol]=j-n1;
}
}

g<<nrsol<<"\n";
for (i=1;i<=min(1000,nrsol);i++) g<<sol[i]<<" ";

    return 0;
}