Pagini recente » Cod sursa (job #6624) | Cod sursa (job #2977917) | Cod sursa (job #2847004) | Cod sursa (job #22965) | Cod sursa (job #2564329)
#include <iostream>
#include <fstream>
#include <string>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
string x, y;
int lps[2000010];
int rez[1010];
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;
int k = 0;
while(i < n)
{
if(x[i] == y[j])
{
i++;
j++;
}
if(j == m)
{
if(k < 1000)
rez[k++] = i - j;
else
break;
j = lps[j - 1];
}
else if(i < n && x[i] != y[j])
{
if(j == 0)
i++;
else
j = lps[j-1];
}
}
k = min(k, 1000);
out << k << '\n';
for(int i = 0; i < k; i++)
out << rez[i] << ' ';
}
int main()
{
in >> y >> x;
buildLps();
solveKMP();
return 0;
}