Pagini recente » Monitorul de evaluare | Cod sursa (job #3310346) | Cod sursa (job #3316288) | Cod sursa (job #3310359) | Cod sursa (job #1189211)
#include <fstream>
#include <cstring>
#include <vector>
using namespace std;
ifstream F("strmatch.in");
ofstream G("strmatch.out");
const int N = 2000010;
char a[2*N],b[N];
int Z[2*N],n,m;
int main()
{
F>>a>>b;
n = strlen(a);
m = strlen(b);
for (int i=n,j=0;i<n+m;++i,++j) a[i] = b[j];
int aux = m;
m = n;
n = aux+m;
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-l+1] == a[r+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-l+1] == a[r+1] && r+1 < n ) ++r;
Z[i] = r-l+1;
}
}
int co = 0;
vector<int> ans;
for (int i=1;i<n;++i)
if ( Z[i] >= m && i > m )
{
++co;
if ( ans.size() < 1000 )
ans.push_back(i-m);
}
G<<co<<'\n';
for (size_t i=0;i<ans.size();++i)
G<<ans[i]<<' ';
G<<'\n';
}