Pagini recente » Cod sursa (job #153812) | Cod sursa (job #865885) | Cod sursa (job #913089) | Cod sursa (job #2122232) | Cod sursa (job #1358083)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
ifstream F("strmatch.in");
ofstream G("strmatch.out");
const int N = 2000010;
int z[N*2],n,m;
char a[N*2];
int cans;
vector<int> ans;
int main()
{
F>>(a+1);
m = strlen(a+1);
F>>(a+m+1);
n = strlen(a+1);
int l = 0 , r = 0;
for (int i=2;i<=n;++i)
if ( i > r )
{
if ( a[i] != a[1] ) continue;
l = r = i;
while ( a[r+1] == a[r-l+2] && r+1 <= n )
++r;
z[i] = r-l+1;
}
else
{
if ( i + z[i-l+1] - 1 < r )
z[i] = z[i-l+1];
else
{
l = i;
while ( a[r+1] == a[r-l+2] && r+1 <= n )
++r;
z[i] = r-l+1;
}
}
//for (int i=1;i<=n;++i) cerr<<z[i]<<' ';
for (int i=m+1;i<=n;++i)
if ( z[i] >= m )
{
cans++;
if ( cans <= 1000 )
ans.push_back(i-m);
}
G<<cans<<'\n';
for (int i=0;i<int(ans.size());++i)
G<<ans[i]-1<<' ';
G<<'\n';
}