Pagini recente » Cod sursa (job #334505) | Cod sursa (job #1570123) | Cod sursa (job #1534932) | Cod sursa (job #2392267) | Cod sursa (job #2883967)
#include <bits/stdc++.h>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
int N,M,pi[2000005];
string A,B;
void make_prefix(void)
{
int i, q = 0;
for (i = 2, pi[1] = 0; i <= M; ++i)
{
while (q && A[q+1] != A[i])
q = pi[q];
if (A[q+1] == A[i])
++q;
pi[i] = q;
}
}
int main()
{
f>>A>>B;
M=A.size();
N=B.size();
A=" "+A;
B=" "+B;
make_prefix();
int poz=0;
vector<int>elem;
for(int i=1; i<=N; i++)
{
while( poz&&A[poz+1]!=B[i] ) poz=pi[poz];
if(A[poz+1]==B[i]) poz++;
if(poz==M)
{
poz=pi[poz];
if(elem.size()<1000) elem.push_back(i-M);
}
}
g<<elem.size()<<'\n';
for(int i=0; i<elem.size(); i++) g<<elem[i]<<' ';
return 0;
}