Pagini recente » Rating Afloarei Iustin (afloareiiustin02) | Cod sursa (job #633704) | Cod sursa (job #1648017) | Cod sursa (job #1358582) | Cod sursa (job #1691529)
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include <fstream>
#include <string>
#include <vector>
#include <queue>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmath.out");
string pattern, s;
vector<int> v;
vector<int> build_prefix(string);
void KMP();
int main()
{
fin >> pattern;
fin >> s;
v=build_prefix(pattern);
KMP();
/*
for (int i = 0; i < v.size(); i++)
fout << v[i];
fout << '\n' << pattern;
*/
return 0;
}
vector<int> build_prefix(string p)
{
vector<int> v;
v.reserve(p.size());
v.push_back(0);
if (p[0] == p[1])
v.push_back(1);
else
v.push_back(0);
for (int i = 2; i < p.size(); i++)
{
if (p[i] != p[0])
{
if (p[i] != p[v[i - 1] ])
v.push_back(0);
else
v.push_back(v[i - 1] + 1);
}
else
v.push_back(1);
}
return v;
}
void KMP()
{
int k=0;
bool ok;
queue<int> q;
for (int i = 0; i < s.size(); i++)
{
ok = 0;
while (k<pattern.size() && s[i] == pattern[k] )
{
k++; i++;
ok = 1;
}
if (k == pattern.size())
{
q.push(i - k);
k = v[k-1]-1;
i--;
i--;
}
else
{
if (ok)
{
k = v[k] - 1;
i--;
if (k < 0)
k = 0;
}
else
k = 0;
}
}
fout << q.size()<<'\n';
while (!q.empty())
{
fout << q.front() << ' ';
q.pop();
}
}