Pagini recente » Cod sursa (job #714919) | Cod sursa (job #781332) | Cod sursa (job #1594640) | Cod sursa (job #1844117) | Cod sursa (job #2303181)
#include <fstream>
#include <vector>
#include <string>
#define input "strmatch.in"
#define output "strmatch.out"
#define NMAX 2000005
using namespace std;
ifstream in(input);
ofstream out(output);
vector < int > positions;
string model, pattern;
int urmator[NMAX];
void Read_Data()
{
in >> pattern >> model;
}
void Prefix()
{
int pivot = -1;
for (unsigned i = 1; i < pattern.size(); i++)
{
while (pivot > -1 && pattern[pivot + 1] != pattern[i]) pivot = urmator[pivot];
if (pattern[pivot + 1] == pattern[i]) pivot++;
urmator[i] = pivot;
}
}
void String_Match()
{
int pivot = -1;
for (unsigned i = 0; i < model.size(); i++)
{
while (pivot > -1 && pattern[pivot + 1] != model[i]) pivot = urmator[pivot];
if (pattern[pivot + 1] == model[i]) pivot++;
if (pivot == pattern.size() - 1)
{
if (positions.size() < 1000)
positions.push_back(i - pivot);
else break;
pivot = urmator[pivot];
}
}
}
void Print_Sol()
{
out << positions.size() << "\n";
for (unsigned i = 0; i < positions.size(); i++)
out << positions[i] << " ";
}
int main()
{
Read_Data();
Prefix();
String_Match();
Print_Sol();
return 0;
}