Pagini recente » Cod sursa (job #1433674) | Cod sursa (job #2954571) | Cod sursa (job #907888) | Cod sursa (job #1943264) | Cod sursa (job #1345462)
#include <stdio.h>
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
using namespace std;
typedef int ull;
inline ull minim(ull a, ull b) {
return (a < b) ? a : b;
}
#define NMAX 2000005
void make_prefix(string A, vector<ull> & pi) {
int i, q = 0;
int n = A.length();
pi[0] = pi[1] = 0;
for (i = 2; i <= n; ++i) {
int j = pi[i - 1];
for (;;) {
if (A[j] == A[i - 1]) {
pi[i] = j + 1;
break;
}
if (j == 0) {
pi[j] = 0;
break;
}
j = pi[j];
}
}
}
int main(void) {
int i, q = 0, n = 0;
ifstream iff("strmatch.in");
ofstream off("strmatch.out");
string A,B;
iff >> A >> B;
vector<ull> pos;
vector<ull> pi(A.length() + 1, 0);
make_prefix(A, pi);
for (i = 0; i < B.length(); ++i) {
while (q && A[q] != B[i])
q = pi[q];
if (A[q] == B[i])
++q;
if (q == A.length()) {
q = pi[A.length()];
++n;
pos.push_back(i - A.length() + 1);
}
}
off << pos.size();
if (pos.size()) {
off << endl;
}
for (int i = 0; i <1000; ++i) {
off << pos[i] << " ";
}
off.close();
}