Cod sursa(job #847890)

Utilizator OpportunityVlad Negura Opportunity Data 4 ianuarie 2013 16:58:15
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.81 kb
#include <fstream>
#include <string>
 
using namespace std;
 
ifstream fi("strmatch.in");
ofstream fo("strmatch.out");
 
string a,b;
long h1,k1,h2,k2,n,m,i,v[10000000],vn;
const long mod1=10000021,mod2=90007;
 
 
int main(){
     
    fi >> a >> b; n = a.size(); m = b.size();
    if (n>m) { fo << "0\n"; return 0; }
     
    for (i=0; i<n; i++){
        k1 = (k1+a[i])%mod1; k2 = (k2+a[i])%mod2;
        h1 = (h1+b[i])%mod1; h2 = (h2+b[i])%mod2;
    }
     
    if ((k1==h1)&&(k2==h2)&&(b.substr(0,n)==a)) vn++;
     
    for (i=n; i<m; i++){
        h1 = (h1-b[i-n]+b[i])%mod1; h2 = (h2-b[i-n]+b[i])%mod2;
        if ((k1==h1)&&(k2==h2)&&(b.substr(i-n+1,n)==a)) v[vn++] = i-n+1;
    }
     
    fo << vn << "\n";
    for (i=0; i<vn && vn<1000; i++) fo << v[i] << " ";
     
    return 0;
}