Cod sursa(job #3261959)

Utilizator XIIs12sPeteleu Denis Andrei XIIs12s Data 7 decembrie 2024 22:17:40
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.18 kb
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
#define minim(a,b) ((a<b) ? a:b)
#define nMax 2000005
int M,N;
char a[nMax], b[nMax];
int pi[nMax], pos[nMax];

void make_prefix()
{
    int i,q=0;
    for(i=2,pi[1]=0;i<=M;i++)
    {
        while(q&&a[q+1]!= a[i])
            q=pi[q];
        if(a[q+1]==a[i])
            ++q;
        pi[i]=q;
    }
}
int main()
{
   int i,q=0,n=0;
   f>>a;
   f>>b;
   for (; (a[M] >= 'A' && a[M] <= 'Z') || (a[M] >= 'a' && a[M] <= 'z')|| (a[M] >= '0' && a[M] <= '9'); ++M);
	for (; (b[N] >= 'A' && b[N] <= 'Z') || (b[N] >= 'a' && b[N] <= 'z')|| (b[N] >= '0' && b[N] <= '9'); ++N);
   for(i=M;i>=0;i--) a[i]= a[i-1]; a[0]=' ';
    for(i=N;i>=0;i--) b[i]= b[i-1]; b[0]=' ';
    make_prefix();
    for(i=1;i<=N;i++)
    {
        while(q&&a[q+1]!=b[i])
            q=pi[q];
        if(a[q+1]==b[i])
            ++q;
        if(q==M)
        {
            q=pi[M];
            ++n;
            if(n<=1000)
                pos[n]=i-M;
        }
    }
    g<<n<<endl;
    for(i=1;i<=minim(n,1000);i++)
        g<<pos[i]<<" ";
    return 0;
}