Pagini recente » Cod sursa (job #1808107) | Cod sursa (job #1857864) | Cod sursa (job #1031196) | Cod sursa (job #228619) | Cod sursa (job #2564306)
#include <iostream>
#include <fstream>
#include <string>
#include <queue>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
string x, y;
int lps[2000010];
void buildLps()
{
int sze = y.size();
int len = 0, i = 1;
lps[0] = 0;
while(i < sze)
{
if(y[i] == y[len])
{
len++;
lps[i] = len;
i++;
}
else
{
if(len != 0)
len--;
else
{
len = 0;
lps[i] = 0;
i++;
}
}
}
}
void solveKMP()
{
int n = x.size();
int m = y.size();
int i = 0;
int j = 0;
queue<int> q;
int limit = 1000;
while(i < n && q.size() <= limit)
{
if(x[i] == y[j])
{
i++;
j++;
}
if(j == m)
{
q.push(i - j);
j = lps[j - 1];
}
else if(i < n && x[i] != y[j])
{
if(j == 0)
i++;
else
j = lps[j-1];
}
}
out << q.size() << '\n';
while(!q.empty())
{
out << q.front() << ' ';
q.pop();
}
}
int main()
{
in >> y >> x;
buildLps();
solveKMP();
return 0;
}