Pagini recente » Cod sursa (job #1554677) | Cod sursa (job #2455070) | Cod sursa (job #3202383) | Cod sursa (job #1212771) | Cod sursa (job #2757703)
#include <fstream>
#include <cstring>
using namespace std;
ifstream in ("strmatch.in");
ofstream out ("strmatch.out");
const int dim = 2e6+ 5;
const int baza = 73, mod = 100021;
char a[dim],b[dim];
int hasha;
int sol[dim];
int cnt= 0;
int main() {
in >> (a+1) >> (b+1);
int n = strlen(a+1);
int m = strlen(b+1);
int putere = 1;
for ( int i = 1;i <= n-1; ++i)
putere = (1LL * putere * baza)%mod;
for ( int i = 1; i <= n; ++i) {
hasha = ((1LL * hasha*baza)%mod + a[i])%mod;
}
int hashb = 0;
for ( int i = 1;i <= n; ++i) {
hashb = ((1LL * hashb*baza)%mod + b[i])%mod;
}
if(hashb == hasha)
sol[++cnt] = 1;
for ( int dr = n+1; dr <= m; ++dr) {
hashb = (hashb - ((1LL * b[dr- n] * putere))%mod + mod)%mod;
hashb = ((1LL * hashb*baza))%mod;
hashb = (hashb + b[dr])%mod;
if(hasha == hashb)
sol[++cnt] = dr -n+1;
}
out<<cnt<<'\n';
for(int i=1;i<=cnt && i<=1000;i++)
{
out<<sol[i]-1<<" ";
}
}