Pagini recente » Cod sursa (job #748614) | Cod sursa (job #2035897) | Statistici Delia Dumitrescu (ddeliaioana) | Monitorul de evaluare | Cod sursa (job #2040226)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
vector<int>ans;
#define pb push_back
const int Nmax = 2000000 + 5;
char N[Nmax + 5], H[Nmax + 5];
int n, h, s[Nmax], cnt;
int f = 0;
void afis()
{
fout << ans.size() << '\n';
for(auto i : ans)
fout << i << " ";
}
int main()
{
fin >> (N + 1) >> (H + 1);
n = strlen(N + 1); h = strlen(H + 1);
s[0] = -1;
s[1] = 0;
for(int i = 2; i <= n; ++i)
{
int k = i - 1;
char c = N[i];
while(s[k] != -1 && N[s[k] + 1] != c)
k = s[k];
s[i] = s[k] + 1;
}
f = 0;
for(int i = 1; i <= h; ++i)
{
if(N[f + 1] == H[i])
{
f++;
if(f == n)
{
cnt ++;
if(cnt <= 1000)
ans.pb(i - n);
f = s[f];
}
}
else
{
while(N[s[f] + 1] != H[i] && f != -1)
f = s[f];
}
if(f == -1)f = 0;
}
afis();
return 0;
}