Pagini recente » Cod sursa (job #2670255) | Istoria paginii runda/party_horse_42699 | Cod sursa (job #3179838) | Cod sursa (job #2631259) | Cod sursa (job #1524275)
#include <fstream>
#include <cstring>
#define inFile "strmatch.in"
#define outFile "strmatch.out"
#define maxA 2000010
using namespace std;
int pi[maxA],pos[1100],N;
char A[maxA],B[maxA];
void prefix(char B[])
{
int i,k,l = strlen(B);
pi[1] = 0;
k = 0;
for(i = 2;i < l;i++)
{
while(k > 0 && B[k + 1] != B[i])
k = pi[k];
if(B[k + 1] == B[i])
k++;
pi[i] = k;
}
}
int main()
{
int i,lA,q,lB;
A[0] = B[0] = '0';
ifstream f(inFile);
ofstream g(outFile);
f.getline(B + 1,maxA);
f.getline(A + 1,maxA);
prefix(B);
lA = strlen(A);
lB = strlen(B);
q = 0;
for(i=1;i<lA;i++)
{
while(q > 0 && A[i] != B[q + 1])
q = pi[q];
if(A[i] == B[q + 1])
q++;
if(q == lB - 1)
{
N++;
if(N < 1002)
pos[N] = i - lB + 1;
q = pi[q];
}
}
g<<N<<"\n";
for(i=1;i<=min(N,1000);i++)
g<<pos[i]<<" ";
}