Pagini recente » Cod sursa (job #278004) | Cod sursa (job #2224371) | Cod sursa (job #1879062) | Cod sursa (job #2470871) | Cod sursa (job #2744975)
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <cstring>
#include <queue>
#include <stack>
using namespace std;
ifstream f("strmatch.in");
ofstream o("strmatch.out");
int main()
{
string pattern;
string s;
int printedIndex = 0;
vector<int>ans;
f >> pattern;
f >> s;
vector<int>lsp(pattern.size(), 0);
int j = 0;
for (int i = 1; i < pattern.size(); i++)
{
if (pattern[i] == pattern[j])
{
lsp[i] = ++j;
}
else if (j != 0)
{
j = lsp[i - 1];
}
}
j = 0;
for (size_t i = 0; i < s.size(); i++)
{
if (s[i] == pattern[j])
{
j++;
if (j == pattern.length())
{
printedIndex++;
ans.push_back(i - j + 1);
j = lsp[j - 1];
}
}
else
{
if (j != 0)
{
j = lsp[j - 1];
i--;
}
}
}
o << printedIndex << "\n";
printedIndex = min(1000, printedIndex);
for (size_t i = 0; i < printedIndex; i++)
{
o << ans[i] << " ";
}
}