Pagini recente » Cod sursa (job #2861765) | Cod sursa (job #198466) | Cod sursa (job #1689440) | Cod sursa (job #298491) | Cod sursa (job #1161709)
#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+1]!=A[i]) --k;
if (A[k+1]==A[i]) ++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 (k>0 && A[k+1]!=B[i]) --k;
if (A[k+1]==B[i]) ++k;
if (k==N)
k=pi[N], sol[++dim]=i-N;
}
g<<dim<<'\n'; if (dim>1000) dim=1000;
for (int i=1; i<=dim; ++i)
g<<sol[i]<<' ';
return 0;
}