Cod sursa(job #2413293)

Utilizator smoc_georgemarianSmoc George-Marian smoc_georgemarian Data 23 aprilie 2019 11:40:54
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.96 kb
#include <bits/stdc++.h>
#define NMAX 2000009
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char a[NMAX],b[NMAX];
int lga,lgb,i,j,k;
int vala[NMAX],valb[NMAX];
int nrs;
vector <int> sol;
void citire()
{
  fin>>(a+1)>>(b+1);
  lga=strlen(a+1),lgb=strlen(b+1);
}
int main()
{
   citire();
   k=0;
   for(i=2;i<=lga;i++)
    {
    while(a[k+1]!=a[i] && k)
           k=vala[k];
    if(a[k+1]==a[i])
        k++;
    vala[i]=k;
    }
    if(a[1]==b[1])
        k=1,valb[1]=1;
        else
        k=0;
    for(i=2;i<=lgb;i++)
        {
         while(a[k+1]!=b[i] && k)
                k=vala[k];
         if(a[k+1]==b[i])
            k++;
         valb[i]=k;
         if(k==lga && sol.size()<1000)
            sol.push_back(i-lga),nrs++;
            else
            if(k==lga)
            nrs++;
        }
     fout<<nrs<<'\n';
     for(i=0;i<sol.size();i++)
            fout<<sol[i]<<" ";
    return 0;
}