Pagini recente » Cod sursa (job #1649150) | Cod sursa (job #2585770) | Cod sursa (job #1064428) | Cod sursa (job #1675992) | Cod sursa (job #2674697)
#include <fstream>
#include <vector>
#include <cstring>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
const int NMAX = 2000000;
const long long BASE = 256;
const long long MOD = 1e9 + 7;
char s[1 + NMAX + 1], pat[1 + NMAX + 1];
long long power = 1;
int main() {
int n, m;
fin>>(pat + 1)>>(s + 1);
m = strlen(pat+1);
n = strlen(s+1);
long long p = 0;
long long t = 0;
for( int i = 1; i <= m; i ++ ) {
p = (p * BASE + (long long)pat[i]) % MOD;
t = (t * BASE + (long long)s[i]) % MOD;
if( i < m )
power = (power * BASE) % MOD;
}
vector<int> ans;
for( int i = m; i <= n && ans.size() < 1000; i ++ ) {
if( p == t ) {
int j = 1;
while( s[i - m + j] == pat[j] && j <= m )
j ++;
if( j == m + 1 )
ans.push_back(i - m + 1);
}
t = ( BASE * (t - s[i - m + 1] * power + MOD) % MOD + s[i + 1] ) % MOD;
}
fout<<ans.size()<<"\n";
for( int i = 0; i < ans.size(); i ++ )
fout<<ans[i] - 1<<" ";
return 0;
}