Pagini recente » Cod sursa (job #2484924) | Cod sursa (job #2161312) | Cod sursa (job #3255774) | Cod sursa (job #698358) | Cod sursa (job #2580866)
#include <iostream>
#include <stdio.h>
#include <vector>
#include <cstring>
#include <set>
#include <map>
#include <unordered_map>
#include <utility>
#include <queue>
#include <deque>
#include <stack>
#include <algorithm>
#define nmax 2000010
#define fst first
#define snd second
#define pb push_back
#define MOD 998244353
#define SZ(x) ((int)(x.size()))
using namespace std;
typedef pair<int, int> pii;
typedef long long int ll;
int n, m, len;
int z[2 * nmax];
char a[nmax], b[nmax], c[2 * nmax];
int main()
{
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
scanf("%s", a + 1);
scanf("%s", b + 1);
int n = strlen(a + 1);
int m = strlen(b + 1);
len = n;
for (int i = 1; i <= n; i++) c[i] = a[i];
c[++len] = '@';
for (int i = 1; i <= m; i++) c[++len] = b[i];
z[1] = 0;
int l = 0, r = 0;
for (int i = 2; i <= len; i++) {
if (i > r) {
l = r = i;
while (r <= len && c[r] == c[r - l + 1]) r++;
z[i] = r - l; r--;
}
else
{
int pos = i - l + 1;
if (i + z[pos] <= r) z[i] = z[pos]; else
{
l = i;
while (r <= len && c[r] == c[r - l + 1]) r++;
z[i] = r - l; r--;
}
}
}
vector <int> vc;
for (int i = n + 1; i <= len; i++)
if (z[i] == n) vc.pb(i - n - 2);
printf("%d\n", SZ(vc));
for (int i = 0; i < SZ(vc); i++) printf("%d ", vc[i]);
// IMPORTANT!!!!!
// Are you missing something????
// check limits, int or ll
return 0;
}