Pagini recente » Cod sursa (job #948707) | Cod sursa (job #1246717) | Cod sursa (job #2550796) | Cod sursa (job #223218) | Cod sursa (job #3309150)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
const int NMAX = 2 * 1e6 + 5;
vector<int> lps(NMAX, 0);
void pre_built(string pattern)
{
lps[0] = 0;
int lenght = 0;
int i = 1;
int m = pattern.size();
while (i < m)
{
if (pattern[i] == pattern[lenght])
{
lenght++;
lps[i] = lenght;
i++;
}
else
{
if (lenght > 0)
{
lenght = lps[lenght - 1];
}
else
{
lps[i] = 0;
i++;
}
}
}
}
void kmp(string a, string b)
{
vector<int> pozitii;
int i = 0;
int j = 0;
int n = a.size();
int m = b.size();
while (i < n)
{
if (a[i] == b[j])
{
i++;
j++;
}
else
{
if (j != 0)
j = lps[j - 1];
else
i++;
}
if (j == m)
{
pozitii.push_back(i - j);
j = lps[j - 1];
}
}
fout << pozitii.size() << '\n';
for (int i=0;i<1000;i++)
fout << pozitii[i] << ' ';
}
int main()
{
string a, b;
fin >> b;
fin >> a;
pre_built(b);
kmp(a, b);
}