Pagini recente » Cod sursa (job #2875155) | Cod sursa (job #814562) | Cod sursa (job #1647833) | Cod sursa (job #71583) | Cod sursa (job #2063144)
#include <fstream>;
#include <string>;
#include <vector>;
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
string text, substring;
vector<int> pattern,rez;
void makePattern()
{
for (int i = 1, j = 0; i < substring.length(); i++)
{
while (substring[i] != substring[j] && j > 0)
j = pattern[j - 1];
if (substring[i] == substring[j])
pattern[i] = ++j;
}
}
void searchPattern()
{
for (int i = 0, j = 0; i < text.length(); i++)
{
while (text[i] != substring[j] && j > 0)
j = pattern[j - 1];
if (text[i] == substring[j])
{
if (j == substring.length() - 1)
{
rez.push_back(i - substring.length() + 1);
j = pattern[j];
}
else
j++;
}
}
}
int main() {
fin >> substring >> text;
pattern.reserve(substring.length());
makePattern();
searchPattern();
fout << rez.size() << "\n";
for (int i = 0; i < 1000 && i < rez.size(); i++) {
fout << rez[i]<<" ";
}
}