Pagini recente » Cod sursa (job #898109) | Cod sursa (job #997681) | Cod sursa (job #1230411) | Cod sursa (job #2404131) | Cod sursa (job #784752)
Cod sursa(job #784752)
#include <fstream>
#include <string>
using namespace std;
const int NM = 200002;
const int P = 73;
const int MOD1 = 100007;
const int MOD2 = 100021;
string A,B;
int poz[NM],nr,ha1,ha2,h1,h2,P1,P2;
int main()
{
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int i,N,M;
getline(fin,A); M=A.length();
getline(fin,B); N=B.length();
if(M > N)
{
fout<<"0";
return 0;
}
P1 = P2 = 1;
ha1 = ha2 = 0;
for( i = 0; i < M; ++i)
{
ha1 = ( ha1 * P + A[i] ) % MOD1;
ha2 = ( ha2 * P + A[i] ) % MOD2;
if(i)
{
P1 = ( P1 * P ) % MOD1;
P2 = ( P2 * P ) % MOD2;
}
}
for(i = 0; i < M; ++i)
{
h1 = ( h1 * P + B[i]) % MOD1;
h2 = ( h2 * P + B[i]) % MOD2;
}
if(ha1 == h1 && ha2 == h2)poz[++nr]=0;
for ( i=M; i<N; ++i)
{
h1 = ((h1 - (B[i - M] * P1 ) % MOD1 + MOD1) * P + B[i]) % MOD1;
h2 = ((h2 - (B[i - M] * P2 ) % MOD2 + MOD2) * P + B[i]) % MOD2;
if(ha1 == h1 && ha2 == h2)
{
poz[++nr] = i - M + 1;
}
}
int mm=nr>1000?1000:nr;
fout<<nr<<'\n';
for(i=1;i<=mm;++i)fout<<poz[i]<<' ';
return 0;
}