Pagini recente » Cod sursa (job #1794295) | Cod sursa (job #3284600) | Cod sursa (job #2515740) | Cod sursa (job #2135816) | Cod sursa (job #2531609)
/* https://infoarena.ro/problema/strmatch */
#include <fstream>
#include <cstring>
#define NMax 2000003
#define WMax 1000
using namespace std;
char subsir[NMax], sir[NMax];
int nextState[NMax], matchPos[NMax];
void build_finite_automata(char *s, int n)
{
nextState[0] = nextState[1] = 0;
for (int i = 1, state = 0; i < n; ++i) {
while (0 < state && s[state] != s[i]) {
state = nextState[state];
}
if (s[state] == s[i]) {
state++;
}
nextState[i+1] = state;
}
}
int kmp_match(char *subsir, int n, char *sir, int m)
{
int numMatch = 0;
for (int i = 0, state = 0; i < m; ++i) {
while (0 < state && subsir[state] != sir[i]) {
state = nextState[state];
}
if (subsir[state] == sir[i]) {
state++;
}
if (state == n) {
if (numMatch < WMax) {
matchPos[numMatch] = i-n+1;
}
numMatch++;
state = nextState[state];
}
}
return numMatch;
}
int main()
{
ifstream f("strmatch.in");
ofstream g("strmatch.out");
f.getline(subsir, NMax);
f.getline(sir, NMax);
int n = strlen(subsir);
int m = strlen(sir);
build_finite_automata(subsir, n);
int numMatch = kmp_match(subsir, n, sir, m);
g << numMatch << "\n";
numMatch = (WMax < numMatch) ? WMax : numMatch;
for (int i = 0; i < numMatch; ++i) {
g << matchPos[i] << " ";
}
f.close();
g.close();
return 0;
}