Pagini recente » Cod sursa (job #1687301) | Cod sursa (job #101585) | Cod sursa (job #603307) | Cod sursa (job #1340029) | Cod sursa (job #895499)
Cod sursa(job #895499)
#include<fstream>
#include<cstring>
#include<vector>
#define Nmax 2000009
#define pb push_back
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
int nr,phi[Nmax],i,q,N,M;
char s1[Nmax],s2[Nmax];
vector<int> Q;
void prefix()
{
phi[0]=0;
i=1;
q=0;
while (i<N)
{
while (s1[q]!=s1[i] && q)
q=phi[q-1];
if (s1[q]==s1[i]) q++;
phi[i]=q;
i++;
}
}
void KMP()
{
i=0;
q=0;
while (i<M)
{
while (s1[q]!=s2[i] && q)
q=phi[q-1];
if (s1[q]==s2[i]) q++;
if (q==N)
{
nr++;
if (nr<=1000) Q.pb(i-N+1);
}
i++;
}
}
int main()
{
in.getline(s1,Nmax);
in.getline(s2,Nmax);
N=strlen(s1);
M=strlen(s2);
prefix();
KMP();
out<<nr<<'\n';
for (i=0;i<Q.size();i++)
out<<Q[i]<<' ';
}