Pagini recente » Cod sursa (job #2637037) | Cod sursa (job #890338) | Cod sursa (job #2096243) | Cod sursa (job #612143) | Cod sursa (job #1923393)
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
string t, p;
vector<int> rez;
void citeste()
{
getline(cin, p);
getline(cin, t);
}
void kmp()
{
int n = t.size();
int m = p.size();
int pi[m];
pi[0] = 0;
int k = 0;
for(int i = 1; i < m; ++i)
{
while(k > 0 && p[k+1] != p[i])
k = pi[k-1];
if(p[k+1] == p[i])
k = k+1;
pi[i] = k;
}
k = 0;
for(int i = 0; i < n; ++i)
{
while(k > 0 && p[k+1] != t[i])
k = pi[k-1];
if(p[k+1] == t[i])
k = k+1;
if(k == m-1 && i-m+1 >= 0)
{
rez.push_back(i-m+1);
k = pi[k-1];
}
}
}
void afis()
{
int len = rez.size(), minim = min(len, 1000);
printf("%d\n", len);
for(int i = 0; i < min(len, 1000); ++i)
printf("%d ", rez[i]);
}
int main()
{
ios_base::sync_with_stdio(false);
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
citeste();
kmp();
afis();
return 0;
}