Pagini recente » Cod sursa (job #1944728) | Cod sursa (job #2735872) | Cod sursa (job #2284576) | Cod sursa (job #1071544) | Cod sursa (job #2794868)
#include <iostream>
#include <fstream>
#include <stdio.h>
#include <string>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
const int MAXPOZ = 1000;
const int MOD1 = 666031;
const int MOD2 = 1000007;
const int BASE = 256;
int poz[MAXPOZ];
string str;
int size_str;
string pattern;
int size_pattern;
int main(){
in>>pattern>>str;
//out<<pattern<<str<<'\n';
size_str = str.size();
size_pattern = pattern.size();
bool foundPattern;
int i, j;
int patternCode1, patternCode2;
int strCode1, strCode2;
int pow1, pow2;
patternCode1 = 0;
patternCode2 = 0;
strCode1 = 0;
strCode2 = 0;
pow1 = 1;
pow2 = 1;
for( i = 0; i < size_pattern; i++ ){
patternCode1 = ( patternCode1 * BASE + pattern[i] ) % MOD1;
patternCode2 = ( patternCode2 * BASE + pattern[i] ) % MOD2;
strCode1 = ( strCode1 * BASE + str[i] ) % MOD1;
strCode2 = ( strCode2 * BASE + str[i] ) % MOD2;
if( i > 0 ){
pow1 = pow1 * BASE % MOD1;
pow2 = pow2 * BASE % MOD2;
}
}
j = 0;
foundPattern = 0;
i = size_pattern;
//out<<patternCode1<<" "<<patternCode2<<'\n';
//out<<strCode1<<" "<<strCode2<<'\n';
while( i <= size_str ){
//out<<i<<" "<<str[i]<<" "<<j<<" "<<foundPattern<<'\n';
//out<<patternCode1<<" "<<patternCode2<<'\n';
//out<<strCode1<<" "<<strCode2<<'\n';
if( patternCode1 == strCode1 && patternCode2 == strCode2 ){
foundPattern = 1;
if( j < 1000 )
poz[j] = i - size_pattern;
}
else
foundPattern = 0;
strCode1 = strCode1 - str[i - size_pattern] * pow1 % MOD1;
strCode2 = strCode2 - str[i - size_pattern] * pow2 % MOD2;
if( strCode1 < 0 )
strCode1 += MOD1;
if( strCode2 < 0 )
strCode2 += MOD2;
strCode1 = ( strCode1 * BASE + str[i] ) % MOD1;
strCode2 = ( strCode2 * BASE + str[i] ) % MOD2;
i++;
j += foundPattern;
}
out<<j<<'\n';
for( i = 0; i < j; i++ )
out<<poz[i]<<" ";
return 0;
}