Pagini recente » Cod sursa (job #53063) | Cod sursa (job #33055) | Cod sursa (job #663512) | Cod sursa (job #430398) | Cod sursa (job #3151739)
#include <fstream>
#include <algorithm>
#include <vector>
#include <climits>
#include <stack>
#include <cmath>
#include <queue>
#define ll long long
using namespace std;
const int NMAX = 2e6;
int z[2 * NMAX + 1];
string s;
void zfunction()
{
z[0] = 0;
int i, l, r;
l = r = 0;
for (i = 1; i < s.size(); i++)
{
if (i <= r)
z[i] = min(z[i - l], r - i + 1);
while (i + z[i] < s.size() and s[i + z[i]] == s[z[i]])
z[i]++;
if (r < i + z[i] - 1)
{
l = i;
r = i + z[i] - 1;
}
}
}
vector <int> sol;
signed main()
{
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
int i;
string a;
cin >> a;
cin >> s;
s = a + s;
zfunction();
for (i = a.size(); i < s.size() and sol.size() <= 1000; i++)
if (z[i] >= a.size())
{
sol.push_back(i - a.size());
}
cout << sol.size() << "\n";
for (int x : sol)
cout << x << " ";
}