Pagini recente » Cod sursa (job #3215236) | Cod sursa (job #1022408) | Cod sursa (job #2546195) | Cod sursa (job #1022382) | Cod sursa (job #3038659)
#include <iostream>
#include <cstring>
#include <vector>
using namespace std;
const int NMAX = 2e6 + 1;
char s[NMAX],t[NMAX]; int pi[NMAX];
void kmp()
{
int n = strlen(s + 1),j = 0;
for(int i = 2; i <= n ; i++)
{
while(j && s[i] != s[j + 1]) j = pi[j];
if(s[i] == s[j + 1]) j++;
pi[i] = j;
}
}
int main() {
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
cin.getline(s + 1,NMAX);
cin.getline(t + 1,NMAX);
int j = 0,cnt = 0; int n = strlen(t + 1),m = strlen(s + 1);
kmp(); vector<int> ans = {0}; int sz = 0;
for(int i = 1; i <= n ; i++)
{
while(j && t[i] != s[j + 1]) j = pi[j];
if(t[i] == s[j + 1]) j++;
if(j == m)
{
sz++;
if(sz <= 1000) ans.emplace_back(i - m);
j = pi[m];
}
}
cout << sz; for(int i = 1; i <= min(sz,1000); i++) cout << ans[i] << " ";
cout << '\n';
return 0;
}