Cod sursa(job #847893)

Utilizator OpportunityVlad Negura Opportunity Data 4 ianuarie 2013 17:00:01
Problema Potrivirea sirurilor Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 0.69 kb
#include <fstream>
#include <string>
  
using namespace std;
  
ifstream fi("strmatch.in");
ofstream fo("strmatch.out");
  
string a,b;
int h,k,n,m,i,v[3000000],vn;
const int mod=10000021;
  
  
int main(){
      
    fi >> a >> b; n = a.size(); m = b.size();
    if (n>m) { fo << "0"; return 0; }
      
    for (i=0; i<n; i++){
        k += a[i] % mod;
        h += b[i] % mod;
    }
      
    if ((k==h)&&(b.substr(0,n)==a)) vn++;
      
    for (i=n; i<m; i++){
        h = (h-b[i-n]+b[i])%mod;
        if ((k==h)&&(b.substr(i-n+1,n)==a)) v[vn++] = i-n+1;
    }
      
    fo << vn << "\n";
    for (i=0; i<vn && i<1000; i++) fo << v[i] << " ";
      
    return 0;
}