Pagini recente » Cod sursa (job #1947680) | Cod sursa (job #2086264) | Cod sursa (job #2096174) | Cod sursa (job #685317) | Cod sursa (job #947306)
Cod sursa(job #947306)
///gasirea numarului de aparitii a sirului a in sirul b
#include <fstream>
#include <cstring>
#define In "strmatch.in"
#define Out "strmatch.out"
#define Nmax 2000010
using namespace std;
char A[Nmax],B[Nmax];
int pi[Nmax],sol[Nmax],n,m;//(pi[i]<i)
//pi[i] = k,k este lungimea celui mai lung prefix a lui Ai(prefix de lungime i lui A)
//egal cu sufixul de lungime k a lui Ai
inline void Citire()
{
ifstream f(In);
f>>(A+1)>>(B+1);
n = strlen(A+1);
m = strlen(B+1);
f.close();
}
inline void Prefix()
{
int i,ind = 0;
pi[1] = 0;
for(i=2;i<=n;i++)
{
while(ind>0 && A[ind+1]!=A[i])
ind = pi[ind];
if(A[ind+1]==A[i])
ind++;
pi[i] = ind;
}
}
inline void KMP()
{
int i,ind = 0;
for(i=1;i<=m;i++)
{
while(ind>0 && A[ind+1]!=B[i])
ind = pi[ind];
if(A[ind+1]==B[i])
ind++;
if(ind==n)
{
ind = pi[ind];
if(sol[0]<1000)
sol[++sol[0]] = i;
}
}
}
inline void Afisare()
{
ofstream g(Out);
int i;
g<<sol[0]<<"\n";
for(i=1;i<=sol[0];i++)
g<<sol[i]-n<<" ";
g<<"\n";
g.close();
}
int main()
{
Citire();
Prefix();
KMP();
Afisare();
return 0;
}