Cod sursa(job #2193875)

Utilizator gabiluciuLuciu Gabriel gabiluciu Data 11 aprilie 2018 18:32:57
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.07 kb
#include <bits/stdc++.h>
#define MAXIM 2000000
using namespace std;
char s[MAXIM],t[MAXIM];
int hash1(string s){
    unsigned long long x = 0;
    for(string::iterator i = s.begin();i!=s.end();++i)
        x+= (int)*i % 101 ;
    return x%100007;
}

int n;
vector<int> potriv;
void Print(vector<int> v){
    for(vector<int>::iterator i= v.begin();i!=v.end();++i)
        cout<< *i << ' ';
    cout<<"\n";
}
int main()
{
    freopen("strmatch.in", "r", stdin);
    freopen("strmatch.out", "w", stdout);
    cin>>s>>t;
    string s1,t1;
    for(int i=0;i<strlen(s);++i){
        s1.push_back(s[i]);
        t1.push_back(t[i]);
    }
    if(s1==t1){
        ++n;
        potriv.push_back(0);
    }
    int hs1 = hash1(s1);
    for(int i=strlen(s);i<strlen(t);++i){
        t1.erase(t1.begin());
        t1.push_back(t[i]);
        if(hs1=hash1(t1))
        if(s1==t1){
                ++n;
                if(n<1000)
                    potriv.push_back(i-strlen(s)+1);
            }
    }
    cout<< n << '\n';
    Print(potriv);
    return 0;
}