Pagini recente » Cod sursa (job #3264961) | Cod sursa (job #1653904) | Cod sursa (job #2431310) | Cod sursa (job #896394) | Cod sursa (job #2538390)
#include <bits/stdc++.h>
using namespace std;
ifstream fin ( "strmatch.in" );
ofstream fout ( "strmatch.out" );
void read ( );
void preprocess ( );
void solve ( );
void afis ( );
string pat;
string cuvant;
vector < int > v;
vector < int > sol;
int k;
int main ( )
{
read ( );
preprocess ( );
solve ( );
afis ( );
}
void afis ( )
{
fout << k << '\n';
for ( int i = 0; i < k; i++ )
fout << sol[i] << ' ';
exit ( 0 );
}
void solve ( )
{
int lng = cuvant.size();
int lg = pat.size();
int j = 0;
for ( int i = 0; i < lng; i++ )
{
if ( cuvant[i] == pat[j] )
{
if ( j == lg-1 )
{
sol.push_back(i-j);
k++;
if(k == 1000)
afis ( );
j = v[j];
}
else
j++;
}
else
{
while ( j && pat[j]!= cuvant[i] )
j = v[j-1];
if ( pat[j] == cuvant[i] )
j++;
}
}
}
void preprocess ( )
{
int lng = pat.size();
v.reserve ( lng+1 );
v[0] = 0;
int len = 0;
int i = 1;
while ( i < lng )
{
if ( pat[i] == pat[len] )
{
len++;
v[i] = len;
i++;
}
else
{
if ( len )
len = v[len-1];
else
{
v[i] = 0;
i++;
}
}
}
}
void read ( )
{
getline ( fin, pat );
getline ( fin, cuvant );
}