Pagini recente » Cod sursa (job #533841) | Cod sursa (job #3331954) | Cod sursa (job #1975759) | Cod sursa (job #1975756) | Cod sursa (job #3329493)
/// https://www.infoarena.ro/automate-finite-si-kmp
#include <fstream>
#include <cstring>
#include <vector>
using namespace std;
const int NMAX = 2e6 + 2;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char a[NMAX], b[NMAX];
int n, m, pi[NMAX], sol;
vector<int> vsol;
void calcPrefix()
{
int x = -1;
pi[0] = -1;
for(int i = 1; i < n; ++i)
{
while(x >= 0 && a[x + 1] != a[i])
x = pi[x];
if(a[x + 1] == a[i])
++x;
pi[i] = x;
}
}
void potrivireKMP()
{
int x = -1;
for(int i = 0; i < m; ++i)
{
while(x >= 0 && a[x + 1] != b[i])
x = pi[x];
if(a[x + 1] == b[i])
++x;
if(x == n - 1) /// Potrivire
{
if(++sol <= 1000)
vsol.push_back(i - n + 1);
}
}
}
int main()
{
fin >> a >> b;
n = strlen(a), m = strlen(b);
calcPrefix();
potrivireKMP();
fout << sol << "\n";
for(const auto& x : vsol) fout << x << " ";
return 0;
}