Pagini recente » Cod sursa (job #1226849) | Cod sursa (job #459580) | Cod sursa (job #1344356) | Cod sursa (job #3222839) | Cod sursa (job #604678)
Cod sursa(job #604678)
#include <fstream>
#include <string.h>
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;//primul in al 2-lea
lengthA = strlen(A);
lengthB = strlen(B);
computePrefix();
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;
}
}