Pagini recente » Cod sursa (job #37971) | Cod sursa (job #489858) | Cod sursa (job #2920700) | Cod sursa (job #52657) | Cod sursa (job #1412244)
#include <fstream>
#include <cstring>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
int N, M, pi[2000005], K, dim, sol[2000005];
char a[2000005], b[2000005];
void bagapi()
{
for (int i=2; i<=N; ++i)
{
while (K>0 && a[K+1]!=a[i]) K=pi[K];
if (a[K+1]==a[i]) ++K;
pi[i]=K;
}
}
int main()
{
f>>(a+1)>>(b+1);
N=strlen(a+1); M=strlen(b+1);
bagapi(); K=0;
for (int i=1; i<=M; ++i)
{
while (K>0 && a[K+1]!=b[i]) K=pi[K];
if (a[K+1]==b[i]) ++K;
if (K==N)
sol[++dim]=i-N, K=pi[N];
}
g<<dim<<'\n'; dim=min(dim, 1000);
for (int i=1; i<=dim; ++i)
g<<sol[i]<<' ';
return 0;
}