Pagini recente » Cod sursa (job #2459983) | Cod sursa (job #953024) | Cod sursa (job #2049537) | Cod sursa (job #379844) | Cod sursa (job #2975545)
#include<bits/stdc++.h>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
string a, b, sz;
int z[2000005];
void citire()
{
in>>a>>b;
}
vector<int> ans;
void rez()
{
sz = a + '|' + b;
int l=0, r=0;
int n = sz.size();
for ( int i = 1 ; i <= n ; i++ )
{
if ( i <= r )
{
z[i] = min(z[i-l], r - i + 1);
}
while (z[i] + i <= n && sz[z[i]] == sz[i+z[i]])
z[i]++;
if ( i + z[i] - 1 > r )
{
l = i;
r = i + z[i] - 1;
}
}
for ( int i = a.size() + 1 ; i < n ; i++ )
{
if ( z[i] == a.size() )
{
ans.push_back(i-a.size()-1);
}
if ( ans.size() >= 1000 )
break;
}
out<<ans.size()<<'\n';
for ( int x : ans )
{
out<<x<<" ";
}
}
int main()
{
citire();
rez();
return 0;
}