Pagini recente » Cod sursa (job #1490664) | Cod sursa (job #1418818) | Cod sursa (job #82088) | Cod sursa (job #2951067) | Cod sursa (job #2193890)
#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> p;
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;
int LS = strlen(s),LT=strlen(t);
for(int i=0;i<LS;++i){
s1.push_back(s[i]);
t1.push_back(t[i]);
}
if(s1==t1){
++n;
p.push_back(0);
}
int hs1 = hash1(s1);
int ht1 = hash1(t1);
for(int i=1;i<LT;++i){
ht1 = ht1 + t[i+LS-1] - t[i-1];
t1.erase(t1.begin());
t1.push_back(t[i+LS-1]);
if(ht1==hs1){
if(t1==s1){
++n;
if(n<1000)
p.push_back(i);
}
}
}
cout<< n << '\n';
Print(p);
return 0;
}