Pagini recente » Cod sursa (job #1101140) | Cod sursa (job #632920) | Cod sursa (job #2048170) | Cod sursa (job #1923748) | Cod sursa (job #2377129)
//#include "pch.h"
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
long long dp[2000005];
vector <int> ans;
string s;
string pat;
string txt;
void kmp(int n, int l) {
int pos = 0;
for (int i = 2; i < n; ++i) {
dp[i] = dp[i - 1];
while (dp[i] && s[i] != s[dp[i] + 1]) dp[i] = dp[dp[i]];
if (s[i] == s[dp[i] + 1]) dp[i]++;
if (dp[i] == l) {
pos++;
if (pos <= 1000) {
ans.push_back(i-l-dp[i]-1);
}
}
}
}
int main() {
ios::sync_with_stdio(false);
fin.tie(0); fout.tie(0);
int n, l;
fin >> pat;
fin >> txt;
s += '?';
s += pat;
s += '#';
s += txt;
l = pat.size();
n = s.size();
kmp(n, l);
fout << ans.size() << '\n';
for (auto x : ans) fout << x << " ";
}