Pagini recente » Cod sursa (job #1363501) | Cod sursa (job #1580369) | Cod sursa (job #2679986) | Cod sursa (job #2184463) | Cod sursa (job #3212231)
#include <bits/stdc++.h>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
#define pii pair<int, int>
#define pb push_back
#define fi first
#define se second
const int NMAX = 2e6 + 30;
const int INF = 0x3f3f3f3f;
char s[NMAX], t[NMAX];
int pi[NMAX], n, m;
vector<int> ans;
void read()
{
in >> s;
in >> t;
n = strlen(s), m = strlen(t);
for (int i = n; i >= 1; i--)
s[i] = s[i - 1];
for (int i = m; i >= 1; i--)
t[i] = t[i - 1];
cout << n;
}
void sufix()
{
// pi[i] -> cea mai lunga subsecventa din M care incepe in M[i]
///(cel mai lung prefix a lui M care este sufix a lui M[i]);
pi[1] = 0;
for (int i = 2, k = 0; i <= n; i++)
{
while (k > 0 && s[k + 1] != s[i])
k = pi[k];
if (s[k + 1] == s[i])
k++;
pi[i] = k;
}
}
void solve()
{
sufix();
for (int i = 1, k = 0; i <= m; i++)
{
while (k > 0 && s[k + 1] != t[i])
k = pi[k];
if (s[k + 1] == t[i])
k++;
if (k == n)
ans.pb(i - n + 1);
}
out << ans.size() << '\n';
for (auto it : ans)
out << it-1 << ' ';
}
int main()
{
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(false);
read();
solve();
return 0;
}