Cod sursa(job #1496067)

Utilizator nnnmmmcioltan alex nnnmmm Data 4 octombrie 2015 11:18:42
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.08 kb
#include<cstdio>
#include<cstring>
#include<algorithm>
int pi[2000002],rasp[1001];
char p[2000002],s[2000002];
int main()
{
 freopen("strmatch.in","r",stdin);
 freopen("strmatch.out","w",stdout);
 scanf("%s %s",p,s);
 int n=strlen(p);
 for(int i=n;i>=1;i--)
     p[i]=p[i-1];
 int m=strlen(s);
 for(int i=m;i>=1;i--)
     s[i]=s[i-1];
 pi[1]=0;
 for(int i=2;i<=n;i++)
     {
      int k=pi[i-1];
      while(k>0 && p[i]!=p[k+1])
            k=pi[k];
      if(p[i]==p[k+1])
         pi[i]=k+1;
      else
         pi[i]=0;
     }
 /*for(int i=1;i<=n;i++)
     printf("%d ",pi[i]);*/
 int k=0,poz=0;
 for(int i=1;i<=m;i++)
     {
      while(k>0 && s[i]!=p[k+1])
            k=pi[k];
      if(s[i]==p[k+1])
         k++;
      if(k==n)
         {
          if(poz<1000)
             rasp[++poz]=i-n;
          else
             poz++;
         }
     }
 /*for(int i=1;i<=m;i++)
     printf("%d ",d[i]);*/
 printf("%d\n",poz);
 poz=std::min(poz,1000);
 for(int i=1;i<=poz;i++)
     printf("%d ",rasp[i]);
 fclose(stdin);
 fclose(stdout);
return 0;
}