Pagini recente » Cod sursa (job #97464) | Cod sursa (job #2227233) | Cod sursa (job #741143) | Cod sursa (job #1287949) | Cod sursa (job #1133089)
#include <iostream>
#include <string>
#include <stdio.h>
#include <fstream>
using namespace std;
const int Nmax = 2000005;
string A, B;
int T[Nmax];
void build(const string &S)
{
T[0] = -1; T[1] = 0;
int i = 2, tmp = 0; // = T[i-1];
for (;i < S.size() + 1;) {
if (S[tmp] == S[i-1])
T[i++] = ++tmp;
else if (tmp > 0)
tmp = T[tmp];
else T[i++] = 0;
}
}
int main()
{
ifstream f ("strmatch.in");
ofstream g ("strmatch.out");
getline(f, A);
getline(f, B);
int N = A.size();
build(A);
int m = 0, // pozitia de start in B;
i = 0; // pozitia curenta in A;
int cnt = 0;
int match[1005];
while (m + N <= B.size())
{
if (A[i] == B[m+i]) {
i++;
if (i == N) {
if (cnt < 1000) match[cnt] = m;
cnt++;
m = m + i - T[i];
if (T[i] > 0) i = T[i];
else i = 0;
}
} else {
m = m + i - T[i];
if (T[i] > 0) i = T[i];
else i = 0;
}
}
g << cnt << endl;
for (int k = 0; k < 1000 && k < cnt; k++)
g << match[k] << ' ';
g << endl;
return 0;
}