Pagini recente » Cod sursa (job #2050698) | Cod sursa (job #1726489) | Cod sursa (job #215071) | Cod sursa (job #2842898) | Cod sursa (job #3241940)
#include <iostream>
#include <vector>
#include <fstream>
using namespace std;
int main () {
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
string a, b;
fin >> a;
fin >> b;
const int n = a.size();
const int m = b.size();
vector<int>lps(n, 0);
int i = 1, prevLPS = 0;
while(i < n)
{
if(a[i] == a[prevLPS])
{
lps[i++] = ++prevLPS;
}
else if(prevLPS == 0)
{
lps[i++] = 0;
}
else
{
prevLPS = lps[prevLPS - 1];
}
}
i = 0;
int j = 0;
vector<int> res;
while(j < m)
{
if(a[i] == b[j])
{
++i;
++j;
}
else if(i == 0)
{
++j;
}
else
{
i = lps[i - 1];
}
if(i == n)
{
res.push_back(j - n);
}
}
fout << res.size() << '\n';
for(i = 0; i < min(static_cast<int>(res.size()), 1000); i++)
{
fout << i << ' ';
}
return 0;
}