Pagini recente » Cod sursa (job #909210) | Cod sursa (job #20859) | Cod sursa (job #1190319) | Cod sursa (job #80314) | Cod sursa (job #3212575)
#include <bits/stdc++.h>
using namespace std;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
int M, N, cont=0;
char A[2000000], B[2000000];
queue<int> coada;
void search()
{
int i, j;
int h = 1;
int txt = 0;
int model = 0;
int d = 256; int p = 101;
h = pow(d, M-1);
h = h%p;
for(i=0; i<M; i++)
{
model = (model * d + A[i]) % p;
txt = (txt * d + B[i]) % p;
}
for(i=0; i <= N-M; i++)
{
if(model == txt)
{
for(j = 0; j<M; j++)
if(B[i+j] != A[j])
break;
if(j==M)
{
cont++;
coada.push(i);
}
}
if(i < N-M)
{
txt = ( d * (txt - B[i] * h) + B[i+M] ) % p;
if(txt < 0) txt += p;
}
}
}
int main()
{
fin >> A >> B;
M = strlen(A);
N = strlen(B);
search();
fout << cont << "\n";
while(!coada.empty())
{
fout << coada.front() << " ";
coada.pop();
}
return 0;
}