Pagini recente » Cod sursa (job #2704499) | Cod sursa (job #3227153) | Cod sursa (job #203870) | Cod sursa (job #1329627) | Cod sursa (job #1541446)
// infoarenaDFSnonRec.cpp : Defines the entry point for the console application.
//
//#include "stdafx.h"
#include <fstream>
#include <string>
#include <assert.h>
#define MaxN 2000005
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
string s1, s2;
int pi[MaxN];
void build_pi() {
int q = -1;
pi[0] = -1;
for (size_t i = 1; i < s1.length(); ++i) {
while (q > -1 && s1[i] != s1[q + 1])
q = pi[q];
if (s1[i] == s1[q + 1])
++q;
pi[i] = q;
}
}
int main()
{
fin >> s1 >> s2;
build_pi();
int res[10001];
int N = 0;
int q = -1;
for (size_t i = 0; i < s2.length(); ++i) {
while (q > -1 && s2[i] != s1[q + 1]) {
q = pi[q];
}
if (s1[q + 1] == s2[i])
++q;
if (q == s1.length() - 1) {
q = pi[q];
++N;
if (N <= 10000) {
res[N] = i - s1.length();
}
}
}
fout << N << '\n';
for (int i = 1; i <= N; ++i)
fout << res[i] + 1 << ' ';
return 0;
}