Pagini recente » Cod sursa (job #1881721) | Rezultatele filtrării | Cod sursa (job #562958) | Cod sursa (job #2699035) | Cod sursa (job #638889)
Cod sursa(job #638889)
#include <fstream>
#include <cstring>
#define N 2000005
#define MMAX 1005
char A[N];
char B[N];
int pi[N];
int pos[MMAX];
int n, m;
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
void Prefix() {
int p = 0;
pi[0] = 0;
for(int i = 1; i < n; i++) {
while((A[p] != A[i]) && (p != 0))
p = pi[p-1];
if (A[p] == A[i])
p++;
pi[i] = p;
}
}
void Solve() {
int p = 0;
int contor = 0;
for(int i = 0; i < m; i++) {
while((A[p] != B[i]) && (p != 0))
p = pi[p-1];
if(A[p] == B[i]) p++;
if (p == n) {
contor++;
if (contor <= 1000)
pos[contor] = i - n + 1;
p = pi[p - 1];
}
}
g << contor << "\n";
for(int i = 1; i <= min(1000, contor); i++)
g << pos[i] << " ";
}
int main()
{
f >> A >> B;
n = strlen(A);
m = strlen(B);
Prefix();
Solve();
return 0;
}