Pagini recente » Cod sursa (job #918167) | Cod sursa (job #2344938) | Cod sursa (job #2603558) | Cod sursa (job #3198644) | Cod sursa (job #2783532)
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
const int MAXN = (int)2e6 + 5;
int LPS[MAXN];
void calculateLPS(string& p)
{
LPS[0] = -1;
int indexPrefix = -1;
for (int indexSufix = 1; indexSufix < p.size(); indexSufix++)
{
while (indexPrefix > -1 && p[indexPrefix + 1] != p[indexSufix])
{
indexPrefix = LPS[indexPrefix];
}
if (p[indexPrefix + 1] == p[indexSufix])
{
indexPrefix++;
}
LPS[indexSufix] = indexPrefix;
}
}
int main()
{
string model, text;
fin >> model >> text;
calculateLPS(model);
int cnt = 0;
vector<int> pozitii;
pozitii.reserve(1005);
int indexModel = -1;
for (int indexText = 0; indexText < text.size(); indexText++)
{
while (indexModel > -1 && model[indexModel + 1] != text[indexText])
{
indexModel = LPS[indexModel];
}
if (model[indexModel + 1] == text[indexText])
{
indexModel++;
}
if (indexModel == model.size() - 1)
{
cnt++;
indexModel = LPS[indexModel];
if (cnt <= 1000)
pozitii.push_back(indexText - model.size() + 1);
}
}
cout << cnt << '\n';
for (int poz : pozitii)
{
cout << poz << ' ';
}
}
/*
ABA
0 1 2 3 4 5 6 7 8 9 10
C A B B C A B A B A B
*/