Pagini recente » Cod sursa (job #1304696) | Cod sursa (job #3305586) | Cod sursa (job #2698873) | Cod sursa (job #1735774) | Cod sursa (job #547224)
Cod sursa(job #547224)
#include <fstream>
#include <string>
using namespace std;
#define maxSize 2000001
#define maxAnswers 1002
ifstream in("strmatch.in");
ofstream out("strmatch.out");
int lengthB,lengthA,matches;
int pi[maxSize],indexx[maxAnswers];
char A[maxSize];
char B[maxSize];
void computePrefix();
int main()
{
in >> A >> B;
lengthA = strlen(A);
lengthB = strlen(B);
computePrefix();
//potrivire;
int q = 0;
for(int i=0; i<lengthB; i++)
{
while(q && A[q] != B[i])
q = pi[q-1];
if(A[q] == B[i])
q++;
if(q == lengthA)
{
q = pi[lengthA - 1];
if(++matches <= 1000)
indexx[matches] = i - lengthA + 1;
}
}
out << matches << "\n";
int stop = min(matches, 1000);
for(int i=1;i<=stop;i++)
out << indexx[i] << " ";
out << "\n";
in.close();
out.close();
return 0;
}
void computePrefix()
{
int q = 0;
for(int i=1; i<lengthA; i++)
{
while(q && A[q] != A[i])
q = pi[q-1];
if(A[i] == A[q])
q++;
pi[i] = q;
}
}