Pagini recente » Cod sursa (job #720244) | Cod sursa (job #995324) | Cod sursa (job #1069064) | Monitorul de evaluare | Cod sursa (job #1691556)
#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("strmatch.out");
string pattern, s, space(" ");
vector<int> v;
vector<int> build_prefix(string);
void KMP();
int main()
{
fin >> pattern;
fin >> s;
pattern =space+pattern;
//s = space + 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]+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[k + 1] != s[i])
k = v[k];
if (pattern[k + 1] == s[i])
k++;
if (k == pattern.size()-1)
{
k = v[k];
if (q.size() <= 1000)
q.push(i-pattern.size()+2);
}
}
_end:
fout << q.size()<<'\n';
while (!q.empty())
{
fout << q.front() << ' ';
q.pop();
}
}