Pagini recente » Cod sursa (job #913829) | Cod sursa (job #1219701) | Cod sursa (job #2859694) | Cod sursa (job #57883) | Cod sursa (job #2339832)
#include <fstream>
#include <string>
#include <stdio.h>
#include <queue>
#define BAZA 27
#define MOD 666013
using namespace std;
string pattern ;
string s ;
queue <int> st ;
int main() {
ifstream fin ("strmatch.in" ) ;
ofstream fout ("strmatch.out") ;
int n, i, counter, P, Pattern, nr, CP ;
fin >> pattern ;
fin >> s ;
P = 1 ;
Pattern = 0 ;
for (i = 0 ; i < pattern.size() ; i++ ) {
Pattern = ( ( ( Pattern % MOD ) * (BAZA % MOD) ) % MOD + (pattern[i] - 'A' + 1 ) ) % MOD ;
if (i != 0 )
P = (P * BAZA) % MOD ;
}
// fout << P << "\n" ;
if (pattern.size() > s.size() ) {
fout << "0" ;
}
else {
nr = 0 ;
for (i = 0 ; i < pattern.size() ; i++ )
nr = ( (nr % MOD ) * (BAZA % MOD) + ( s[i] - 'A' + 1 ) % MOD ) % MOD ;
//fout << "nr = " << nr << "\n" ;
if (nr == Pattern )
st.push(0) ;
for (i = pattern.size() ; i < s.size() ; i++ ) {
nr = ( nr - ( ( (s[i-pattern.size()]- 'A' + 1 ) % MOD ) * ( P % MOD ) ) + MOD ) % MOD ;
nr = ( (nr * (BAZA % MOD ) ) % MOD + ( s[i] - 'A' + 1 ) % MOD ) % MOD ;
//fout << "i = " << i+1 << " nr = " << nr << "\n" ;
if (nr == Pattern )
st.push(i - pattern.size()) ;
}
fout << st.size() << "\n" ;
while (!st.empty()) {
fout << st.front()+1 << " " ;
st.pop() ;
}
}
return 0 ;
}