Pagini recente » Cod sursa (job #2018355) | Rating andrew t (yoshicumin3) | Cod sursa (job #228345) | Cod sursa (job #1168928) | Cod sursa (job #1881818)
#include <bits/stdc++.h>
#define IOS ios_base::sync_with_stdio(0);
#define tie cin.tie(0);
#define mp make_pair
#define ll long long
#define PII pair<int, int>
#define PLL pair<ll, ll>
#define zeros(x) ( (x ^ (x - 1)) & x )
using namespace std;
int n, v[2000100];
string s, S;
vector < int > V;
void prefix()
{
int i = 0;
for (int j = 1; j < s.size();)
{
if (s[i] == s[j])
{
v[j] = i + 1;
i++, j++;
}else
{
if (i != 0)
i = v[i - 1];
else
v[j] = 0, j++;
}
}
}
void solve()
{
int i = 0, j = 0;
while (i < S.size())
{
if (S[i] == s[j]) i++, j++;
else if (j != 0) j = v[j - 1];
else i++;
if (j == s.size()) V.push_back(i - j);
}
}
int main(){
IOS tie
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
cin >> s;
cin >> S;
prefix();
solve();
cout << V.size() << "\n";
int sz = V.size();
for (int i = 0; i < min(sz, 1000); i++)
cout << V[i] << " ";
cerr << "Fucking time elapsed: " << clock() * 1000.0 / CLOCKS_PER_SEC << " ms" << '\n';
return 0;
}