Pagini recente » Cod sursa (job #570921) | Cod sursa (job #1040067) | Cod sursa (job #3315891) | Cod sursa (job #3323143) | Cod sursa (job #3325286)
#include<bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
typedef long long ll;
typedef long double ld;
const int N = 4e6 + 5;
int n, p[N], rasp, l;
string s, t;
/**
ABA#CABBCABABAB
p[i - 1] + 1 = c?
p[p[i - 1] + 1] = c?
*/
int main()
{
fin >> s >> t;
l = s.length();
s = ' ' + s + '#' + t;
n = s.length() - 1;
for (int i = 2; i <= n; i++)
{
int u = p[i - 1];
while (u > 0 && s[u + 1] != s[i])
u = p[u];
if (s[u + 1] == s[i])
u++;
p[i] = u;
}
for (int i = l; i <= n; i++)
if (p[i] == l)
rasp++;
fout << rasp << '\n';
for (int i = l; i <= n; i++)
{
if (i - l > 1000)
break;
if (p[i] == l)
fout << i - 2 * l - 1 << ' ';
}
return 0;
}