Pagini recente » Cod sursa (job #951442) | Cod sursa (job #400100) | Cod sursa (job #515336) | Cod sursa (job #626556) | Cod sursa (job #3299981)
#include <fstream>
#include <string>
#include <vector>
using namespace std;
const int N = 1000;
int main()
{
ifstream in("strmatch.in");
ofstream out("strmatch.out");
string a, b;
in >> a >> b;
int m = (int)a.length();
vector <int> pi(m);
int lung_pref = 0;
pi[0] = lung_pref;
for (int i = 1; i < m; i++)
{
while (lung_pref > 0 && a[i] != a[lung_pref])
{
lung_pref = pi[lung_pref-1];
}
if (a[i] == a[lung_pref])
{
lung_pref += 1;
}
pi[i] = lung_pref;
}
vector <int> poz(N);
int n = (int)b.length(), nr_poz = 0, nr_potriviri = 0;
lung_pref = 0;
for (int i = 0; i < n; i++)
{
while (lung_pref > 0 && b[i] != a[lung_pref])
{
lung_pref = pi[lung_pref-1];
}
if (b[i] == a[lung_pref])
{
lung_pref += 1;
}
if (lung_pref == m)
{
nr_potriviri += 1;
if (nr_poz < N)
{
poz[nr_poz++] = i - m + 1;
}
}
}
out << nr_potriviri << "\n";
for (int i = 0; i < nr_poz; i++)
{
out << poz[i] << " ";
}
in.close();
out.close();
return 0;
}