Pagini recente » Cod sursa (job #397269) | Cod sursa (job #1723319) | Cod sursa (job #2260348) | Cod sursa (job #210808) | Cod sursa (job #1423842)
#include <fstream>
#include <string>
#include <vector>
#include <iostream>
#include <cstring>
#define NMAX 2000010
using namespace std;
vector<int> sol;
char A[NMAX], B[NMAX];
int nrSol=0, lgA, lgB, urm[NMAX];
ifstream f("strmatch.in");
ofstream g("strmatch.out");
void construiesteFunctiaEsec()
{
int i, j=0;
for (i=2; i<=lgA; ++i)
{
while (j>0 && A[j+1]!=A[i])
{
j=urm[j];
}
if (A[j+1]==A[i]) ++j;
urm[i]=j;
}
//for (i=1; i<=lgA; ++i) cout<<urm[i]<<" ";
}
void potrivireaSirurilor()
{
int j=0, i;
for (i=1; i<=lgB; ++i)
{
while (j>0 && A[j+1]!=B[i])
{
j=urm[j];
}
if (A[j+1]==B[i]) ++j;
if (j==lgA)
{
j=urm[j];
++nrSol;
if (sol.size()<1000) sol.push_back(i-lgA);
}
}
}
int main()
{
f.getline(A+1, NMAX);
f.getline(B+1, NMAX);
lgA=strlen(A+1); lgB=strlen(B+1);
construiesteFunctiaEsec();
potrivireaSirurilor();
g<<nrSol<<"\n";
for (int i=0; i<sol.size(); ++i)
g<<sol[i]<<" ";
f.close();
g.close();
return 0;
}