Pagini recente » Cod sursa (job #2508775) | Cod sursa (job #1019700) | Cod sursa (job #714714) | Cod sursa (job #1097283) | Cod sursa (job #1242325)
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream F("strmatch.in");
ofstream G("strmatch.out");
const int N = 2000010;
const int cc = 1000;
string a,b;
int z[N<<1],la;
int main()
{
F>>a>>b;
la = a.size();
a += b;
int n = a.size();
int l = 0 , r = 0;
z[0] = n;
for (int i=1;i<n;++i)
{
z[i] = 0;
if ( l <= i && i <= r )
{
if ( z[i-l] >= r-i+1 ) //
{
l = i;
while ( a[r+1] == a[r-l+1] && r+1 < n ) ++r;
z[i] = r-l+1;
}
else
z[i] = z[i-l];
}
else
if ( a[i] == a[0] )
{
l = r = i;
while ( a[r+1] == a[r-l+1] && r+1 < n ) ++r;
z[i] = r-l+1;
}
//cerr<<z[i]<<' ';
}
vector<int> p;
int ans = 0;
for (int i=la;i<n;++i)
if ( z[i] >= la )
{
++ans;
if ( p.size() < cc )
p.push_back(i-la);
}
G<<ans<<'\n';
for (int i=0;i<p.size();++i)
G<<p[i]<<' ';
G<<'\n';
}