Pagini recente » Cod sursa (job #1799812) | Cod sursa (job #3213641) | Cod sursa (job #785347) | Cod sursa (job #1972) | Cod sursa (job #1362749)
#include <fstream>
#include <string>
#include<vector>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int pi[2000001];
vector<int> sol;
void compute_prefix_function(string p)
{
int m = p.length();
pi[0] = -1;
int k = -1;
for (int q = 1; q < m; q++)
{
while (k > -1 && (p[k + 1] != p[q]))
k = pi[k];
if (p[k + 1] == p[q])
k++;
pi[q] = k;
}
}
void kmp(string p,string s)
{
compute_prefix_function(p);
int n = s.length();
int m = p.length();
int q = -1;
for (int i = 0; i < n; i++)
{
while (q>-1 && (p[q + 1] != s[i]))
q = pi[q];
if (p[q + 1] == s[i])
q = q + 1;
if (q == m - 1)
{
sol.push_back(i - m+1);
q = pi[q];
}
}
}
int main()
{
string p, s;
fin >> p >> s;
kmp(p, s);
fout << sol.size()<<'\n';
for (int i = 0; i<sol.size(); i++)
{
fout << sol[i] << ' ';
}
}