Pagini recente » Cod sursa (job #3303778) | Cod sursa (job #3350023) | Diferente pentru problema/tarc intre reviziile 1 si 6 | Cod sursa (job #3335717) | Cod sursa (job #3329848)
#include <fstream>
#include <cstring>
#include <vector>
using namespace std;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
#define nmax 2000000
char t[nmax + 1];
char p[nmax + 1];
int n, m;
vector<int> sol;
void read()
{
cin >> p >> t;
n = strlen(t);
m = strlen(p);
}
int frontier[nmax + 1];
void build_frontier()
{
int k = 0;
for (int i = 1; i < m; i ++)
{
while (k > 0 && p[k] != p[i])
{
k = frontier[k];
}
if (p[k] == p[i])
{
k ++;
}
frontier[i + 1] = k;
}
}
void kmp()
{
build_frontier();
int q = 0;
for (int i = 0; i < n; i ++)
{
while (q > 0 && p[q] != t[i])
{
q = frontier[q];
}
if (p[q] == t[i])
{
q ++;
}
if (q == m)
{
sol.push_back(i - m + 1);
}
}
}
void print_result()
{
int siz = sol.size();
cout << siz << "\n";
for (int i = 0; i < siz; i ++)
{
cout << sol[i] << " ";
}
}
int main()
{
read();
kmp();
print_result();
return 0;
}