Pagini recente » Cod sursa (job #2150623) | Cod sursa (job #770905) | Cod sursa (job #544304) | Cod sursa (job #3038588)
#include <fstream>
#include <cstring>
#include<vector>
using namespace std;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
const int NMAX = 1e5 + 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 - 1];
if(s[i] == s[j + 1]) j++;
pi[i] = j;
}
}
int main() {
cin >> s + 1 >> t + 1; kmp();
int j = 0; vector<int> ans;
for(int i = 1; i <= strlen(t + 1) ; i++)
{
if(ans.size() >= 1000) break;
while(j && t[i] != s[j + 1]) j = pi[j - 1];
if(t[i] == s[j + 1]) j++;
if(j == strlen(s + 1))
{
ans.emplace_back(i - j);
j = pi[strlen(s + 1)];
}
}
while(ans.size() > 1000) ans.pop_back();
cout << ans.size() << '\n'; for(auto it : ans) cout << it << " ";
return 0;
}