Pagini recente » Cod sursa (job #64971) | Cod sursa (job #343427) | Cod sursa (job #1935863) | Cod sursa (job #1609557) | Cod sursa (job #960446)
Cod sursa(job #960446)
#include <fstream>
#include <vector>
#include <cstring>
using namespace std;
#define in "strmatch.in"
#define out "strmatch.out"
#define N 2000005
char A[N+5], B[N+5], U[N+5], n, m;
vector <int> sol;
int main () {
ifstream fin (in);
fin.getline (A+1, N);
fin.getline (B+1, N);
fin.close();
m = strlen (A+1);
n = strlen (B+1);
int k = 0;
for (int i = 2; i <= m; ++i) {
while (k && A[k + 1] != A[i])
k = U[k];
if (A[k + 1] == A[i])
k++;
U[i] = k;
}
k = 0;
for (int i = 2; i <= n && sol.size() < 1000; ++i) {
while (k && A[k + 1] != B[i])
k = U[k];
if (A[k + 1] == B[i])
k++;
if (k == m) {
k = U[k];
sol.push_back (i - m);
}
}
ofstream fout (out);
fout << sol.size() << "\n";
for (unsigned i = 0; i < sol.size(); ++i)
fout << sol[i] << " ";
fout.close();
return 0;
}