Cod sursa(job #2351781)

Utilizator smoc_georgemarianSmoc George-Marian smoc_georgemarian Data 22 februarie 2019 18:06:36
Problema Potrivirea sirurilor Scor 58
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.35 kb
#include <bits/stdc++.h>
#define NMAX 2000009
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
void citire();
int lg1,lg2;
char a[NMAX],b[NMAX];
int d[NMAX],r[NMAX],cate;
vector <int> v;
int main()
{citire();

    return 0;
}
void citire()
{int i,k=0,gasit;
 fin>>a+1>>b+1;
 lg1=strlen(a+1);
 lg2=strlen(b+1);
 for(i=2;i<=lg1;i++)
        if(a[k+1]==a[i])
           {k++;d[i]=k;}
           else
           {
             while(a[k+1]!=a[i] && k!=0)
                {
                  k=d[k];
                }
              if(a[k+1]==a[i])
                    d[i]=k++;
                    else
                        d[i]=0;

              }
 //   for(i=1;i<=lg1;i++)
   //                 fout<<d[i]<<" ";
 k=0;
 for(i=1;i<=lg2;i++)
        {if(b[i]==a[k+1])
            {
             k++;r[i]=k;
            }
            else
                {while(a[k+1]!=b[i] && k!=0)
                    {
                        k=d[k];
                    }
                 if(a[k+1]==b[i])
                       r[i]=k++;
                    else r[i]=0;

                }
          if(r[i]==lg1)
          {cate++;
          if(cate<=1000)
          v.push_back(i-lg1+1);
          }

        }
   fout<<cate<<'\n';
   for(i=0;i<v.size()    ;i++)
            fout<<v[i]-1<<" ";
}