Pagini recente » Cod sursa (job #770353) | Cod sursa (job #1339077) | Cod sursa (job #1350129) | Cod sursa (job #135627) | Cod sursa (job #2450528)
#include <iostream>
#include <algorithm>
#include <vector>
#include <fstream>
#include <cmath>
#include <iomanip>
#include <queue>
#include <tuple>
#include <limits>
#include <stdio.h>
#include <string.h>
#include <string>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
#define ff first
#define ss second
int lps[2000100];
void calcLPS(string pat)
{
int j = 0, i = 1;
lps[0] = 0;
while(i < pat.size())
{
if (pat[i] == pat[j])
{
lps[i] = j + 1;
j++;
i++;
}
else
{
while (pat[i] != pat[j] && j > 0)
j = lps[j - 1];
if (pat[i] == pat[j])
lps[i] = j + 1;
else
i++;
}
}
}
void kmpSearch(string &needle, string &haystack)
{
vector<int>sol;
int i = 0, j = 0;
while (i < haystack.size())
{
if (needle[j] == haystack[i]) i++, j++;
else
{
while (j > 0 && needle[j] != haystack[i])
j = lps[j - 1];
if (j == 0 && needle[j] != haystack[i]) i++;
}
if (j == needle.size()) {
sol.push_back(i - needle.size());
}
}
fout << sol.size() << '\n';
for (i = 0; i < sol.size(); i++)
{
fout << sol[i] << ' ';
}
}
int main()
{
string needle, haystack;
fin >> needle >> haystack;
calcLPS(needle);
kmpSearch(needle, haystack);
}