Pagini recente » Cod sursa (job #1873881) | Cod sursa (job #2187131) | Cod sursa (job #2714358) | Cod sursa (job #617303) | Cod sursa (job #1161697)
#include <fstream>
#include <cstring>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
int N, M, pi[2000005], dim, sol[2000005], k=0;
char A[2000005], B[2000005];
void build_pi()
{
for (int i=2; i<=N; ++i)
{
while (k>0 && pi[k]!=A[i+1]) --k;
if (A[i+1]==pi[k]) ++k;
pi[i]=k;
}
}
int main()
{
f>>(A+1); f>>(B+1); N=strlen(A+1); M=strlen(B+1);
build_pi(); k=0;
for (int i=1; i<=M; ++i)
{
while (pi[k]!=B[i+1]) --k;
if (pi[k]==B[i+1]) ++k;
if (k==N)
k=pi[N], sol[++dim]=i-N;
}
g<<dim<<'\n'; if (dim>1000) dim=1000;
for (int i=1; i<=1000; ++i)
g<<sol[i]<<' ';
return 0;
}