Pagini recente » Cod sursa (job #1948465) | Cod sursa (job #1805794) | Cod sursa (job #1878287) | Cod sursa (job #2861083) | Cod sursa (job #2794708)
#include <fstream>
#include <string>
#define MOD1 666013
#define MOD2 174763
#define BASE 67
using namespace std;
int pow1, pow2, rez[1001];
string s1, s2;
bool verif( int poz ) {
int k = s1.size() - 1;
while( s1[k] == s2[poz] && k >= 0 ) {
poz--;
k--;
}
if( k == -1 )
return 1;
else
return 0;
}
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 && verif( s1.size() - 1 ) ) {
k++;
rez[k] = 1;
}
for( i = s1.size(); i < s2.size(); i++ ) {
has1 = has1 - ( (long long)s2[i - s1.size()] * pow1 ) % MOD1;
has1 = ( (long long)has1 * BASE + s2[i] ) % MOD1;
has2 = has2 - ( (long long)s2[i - s1.size()] * pow2 ) % MOD2;
has2 = ( (long long)has2 * BASE + s2[i] ) % MOD2;
if( pattern1 == has1 && pattern2 == has2 && verif( i ) && k <= 1000 ) {
k++;
rez[k] = i - s1.size() + 1;
}
}
cout<<k<<"\n";
for( i = 1; i <= k; i++ ) {
cout<<rez[i]<<" ";
}
return 0;
}