Pagini recente » Cod sursa (job #2361437) | Cod sursa (job #2961840) | Cod sursa (job #82553) | Cod sursa (job #749023) | Cod sursa (job #852869)
Cod sursa(job #852869)
#include <fstream>
#include <cstring>
using namespace std;
string P, S;
int k, m, n, sol, pi[2000010], i, t, a[1010];
void prefix()
{
k = 0;
for(i = 2; i <= n; i++)
{
while(k and P[k+1] != P[i]) k = pi[k];
if(P[k+1] == P[i]) k++;
pi[i] = k;
}
}
void go()
{
k = 0;
for(i = 1; i <= m; i++)
{
while(k and P[k+1] != S[i]) k = pi[k];
if(P[k+1] == S[i]) k++;
if(k == n and sol < 1000) a[++t] = i - n;
if(k == n) sol++;
}
}
int main()
{
ifstream fi("strmatch.in");
ofstream fo("strmatch.out");
fi >> P >> S;
n = P.length();
m = S.length();
P = " " + P;
S = " " + S;
prefix();
go();
fo << sol << "\n";
for(i = 1; i <= t; i++) fo << a[i] << " ";
return 0;
}