Cod sursa(job #2345910)

Utilizator Alex221Dumitru Alexandru Alex221 Data 16 februarie 2019 20:10:42
Problema Potrivirea sirurilor Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.96 kb
#include <bits/stdc++.h>
#define MAX 20000001
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char txt[MAX],pat[MAX];
int lps[MAX],i,n,m,len,j,nr,sol[1001];
int main()
{ f.getline(pat,MAX );
  f.getline(txt,MAX);
  n=strlen(txt);
  m=strlen(pat);
  for(i=1;i<=1001;i++)
    sol[i]=-1;
  i=1;
  while(i<m)
  { if(pat[len]==pat[i])
      {   len++;
          lps[i]=len;
          i++;
      }
    else
       {
         if(len!=0)
          len=lps[len-1];
        else
            { lps[i]=0;
                 i++;
            }
       }

  }
  i=j=0;
  while(i<n)
  { if(txt[i]==pat[j])
      { i++;
        j++;
      }
    else
        if(i<n &&pat[j]!=txt[i])
          if(j!=0) j=lps[j-1];
           else i++;
    if(j==m)
    { nr++;
      if(nr<=1000)  sol[nr]=i-j;
      j=lps[j-1];
    }

  }
  g<<nr<<'\n';
  for(i=1;i<=1001;i++)
    if(sol[i]!=-1)
     g<<sol[i]<<" ";
    return 0;
}