Pagini recente » Cod sursa (job #2192160) | Cod sursa (job #1729858) | Cod sursa (job #1911275) | Cod sursa (job #2791832) | Cod sursa (job #2794695)
#include <fstream>
#include <string>
#define MOD1 666013
#define MOD2 174763
#define BASE 67
using namespace std;
int pow1, pow2, rez[2000001];
string s1, s2;
int main() {
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
cin>>s1>>s2;
int i, pattern1 = 0, has1= 0, pattern2 = 0, has2 = 0, k;
pow1 = 1;
pow2 = 1;
pattern1 = s1[0];
has1 = s2[0];
pattern2 = s1[0];
has2 = s2[0];
for( i = 1; i < s1.size(); i++ ) {
pow1 *= BASE;
pow1 %= MOD1;
pattern1 = ( pattern1 * BASE + s1[i] ) % MOD1;
has1 = ( has1 * BASE + s2[i] ) % MOD1;
pow2 *= BASE;
pow2 %= MOD2;
pattern2 = ( pattern2 * BASE + s1[i] ) % MOD2;
has2 = ( has2 * BASE + s2[i] ) % MOD2;
}
k = 0;
if( pattern1 == has1 && pattern2 == has2 ) {
k++;
rez[k] = 1;
}
for( i = s1.size(); i < s2.size(); i++ ) {
has1 = has1 - ( (long long)s2[i - s1.size()] * pow1 ) % MOD1;
has1 = ( has1 * BASE + s2[i] ) % MOD1;
has2 = has2 - ( (long long)s2[i - s1.size()] * pow2 ) % MOD2;
has2 = ( has2 * BASE + s2[i] ) % MOD2;
if( pattern1 == has1 && pattern2 == has2 ) {
k++;
rez[k] = i - s1.size() + 1;
}
}
cout<<k<<"\n";
for( i = 1; i <= k; i++ ) {
cout<<rez[i]<<" ";
}
return 0;
}