Cod sursa(job #2101887)

Utilizator Luca19Hritcu Luca Luca19 Data 8 ianuarie 2018 10:26:53
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.11 kb
#include <fstream>
#include<cstring>
#define nmax 2000005
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
int poz[1002],t[nmax];
char s[nmax],z[nmax];
int c=0,n,m;
void constr_vect_temp()
{
    int j=0;
    for(int i=2;z[i]!=NULL;i++)
    {
        while(z[j+1]!=z[i]&&j)
            j=t[j];
            if(z[j+1]==z[i])
                    j++;
            t[i]=j;
    }
}
 void cauta()
 {
     int j=0;
     int m=strlen(z);
     for(int i=1;s[i]!=NULL;i++)
     {
         while(z[j+1]!=s[i]&&j)
            j=t[j];
         if(z[j+1]==s[i])
            j++;
         if(j==m-1)
         {
             j=t[j];
             c++;
    if(c<=1000)
        poz[c]=i-m+1;
         }
     }
 }

int main()
{
 f.getline(z,nmax);
 f.getline(s,nmax);
 int n=strlen(s);
 int m=strlen(z);
 for(int i=n;i>=1;i--)
        s[i]=s[i-1];
 for(int j=m;j>=1;j--)
    z[j]=z[j-1];
 s[0]=' ';
 z[0]=' ';
 s[n+1]=NULL;
  z[n+1]=NULL;
  constr_vect_temp();
  cauta();
  g<<c<<"\n";
  for(int i=1;i<=min(c,1000);i++)
  {
      g<<poz[i]<<" ";
  }
    return 0;
}