Pagini recente » Cod sursa (job #3304104) | Monitorul de evaluare | Cod sursa (job #660611) | Cod sursa (job #2422392) | Cod sursa (job #718120)
Cod sursa(job #718120)
#include <fstream>
#include <string.h>
#include <algorithm>
#define MAX 2000050
using namespace std;
char A[MAX], B[MAX];
int pfix[MAX], ap[1024], lF, lS, n;
void citire()
{
ifstream in("strmatch.in");
in.getline(A + 1, MAX);
in.getline(B + 1,MAX);
A[0] = B[0] = ' ';
in.close();
}
void getPrefix()
{
int i, q = 0;
for(i = 2, pfix[1] = 0; i <= lF; i++)
{
while(q && A[q + 1] != A[i])
q = pfix[q];
if(A[q + 1] == A[i])
q++;
pfix[i] = q;
}
}
void solve()
{
lF = strlen(A) - 1, lS = strlen(B) - 1;
getPrefix();
int i, q = 0;
for(i = 1; i <= lS; i++)
{
while(q && A[q + 1] != B[i])
q = pfix[q];
if(A[q + 1] == B[i])
q++;
if(q == lF)
{
n++;
if(n <= 1000)
ap[n] = i - lF;
q = pfix[lF];
}
}
}
void afisare()
{
ofstream out("strmatch.out");
out<<n<<'\n';
for(int i = 1; i <= min(1000, n); i++)
out<<ap[i]<<" ";
out.close();
}
int main()
{
citire();
solve();
afisare();
return 0;
}