Cod sursa(job #741457)

Utilizator dutzulBodnariuc Dan Alexandru dutzul Data 26 aprilie 2012 03:26:13
Problema Potrivirea sirurilor Scor 24
Compilator cpp Status done
Runda Arhiva educationala Marime 0.97 kb
#include <fstream>
#define  M 666013
#define LE 2000006

using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
string s1,s2;
int B[LE],A[LE],i,j,sol,R1,Rest,n1,n2,Rgood,H[LE],k;
int comp()
{
   int  I=i;
    for(j=n1/2;j>=1;--j)
      if (A[j]!=B[I--])
        return 0;
    return 1;
}
int main()
{
  f>>s1>>s2;
  n1=s1.length();
  n2=s2.length();

  for(i=0; i<n1; ++i) A[i+1]=s1[i];

  for(i=0; i<n2; ++i) B[i+1]=s2[i];


  for(i=1,Rest=1; i<=n1; ++i)
    {
      Rgood=((Rgood*80)%M+A[i]%M)%M;
      R1=((R1*80)%M+B[i]%M)%M;
      Rest=(Rest*80)%M;
    }
if (Rgood==R1)
++sol,H[++k]=0;

  for(i=n1+1; i<=n2; ++i)
    {
      R1=(R1*80%M+B[i]%M)%M;
      R1=(R1-(B[i-n1]*Rest)%M+M)%M;

      if (R1==Rgood)
        if (comp())
        {
          ++sol;
          if (sol<=1000)
            H[++k]=i-n1;
        }
    }
    g<<sol<<'\n';
for(i=1;i<=k;++i)
g<<H[i]<<" ";
  f.close();
  g.close();
  return 0;
}