Cod sursa(job #1979847)

Utilizator tgm000Tudor Mocioi tgm000 Data 11 mai 2017 15:43:39
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.28 kb
#include<cstdio>
#include<cstring>
#include<vector>
#define MODA 666013
#define MODB 1000007
#define BASE 62
using namespace std;
int poz(char c){
  if(c>='0'&&c<='9')
    return c-'0';
  else if(c>='a'&&c<='z')
    return c-'a'+10;
  else
    return c-'A'+36;
}
char a[2000001];
char b[2000001];
vector <int> v;
int main(){
  int n,m,nr1a,nr1b,nr2a,nr2b,pa,pb,i,ca,cb,nr;
  freopen("strmatch.in","r",stdin);
  freopen("strmatch.out","w",stdout);
  scanf("%s",a);
  n=strlen(a);
  pa=pb=1;
  nr1a=nr1b=0;
  for(i=0;i<n;i++){
    nr1a=(nr1a*BASE+poz(a[i]))%MODA;
    nr1b=(nr1b*BASE+poz(a[i]))%MODB;
    if(i>0){
      pa=(pa*BASE)%MODA;
      pb=(pb*BASE)%MODB;
    }
  }
  scanf("%s",b);
  m=strlen(b);
  nr2a=nr2b=0;
  for(i=0;i<n-1;i++){
    nr2a=(nr2a*BASE+poz(b[i]))%MODA;
    nr2b=(nr2b*BASE+poz(b[i]))%MODB;
  }
  nr=0;
  for(i=n-1;i<m;i++){
    nr2a=(nr2a*BASE+poz(b[i]))%MODA;
    nr2b=(nr2b*BASE+poz(b[i]))%MODB;
    if(nr2a==nr1a&&nr2b==nr1b&&v.size()<1000){
      v.push_back(i-n+1);
      nr++;
    }
    ca=(pa*poz(b[i-n+1]))%MODA;
    nr2a-=ca;
    if(nr2a<0)
      nr2a+=MODA;
    cb=(pb*poz(b[i-n+1]))%MODB;
    nr2b-=cb;
    if(nr2b<0)
      nr2b+=MODB;
  }
  printf("%d\n",nr);
  for(i=0;i<v.size();i++)
    printf("%d ",v[i]);
}