Pagini recente » Cod sursa (job #2138408) | Cod sursa (job #2792793) | Cod sursa (job #99035) | Cod sursa (job #1087457) | Cod sursa (job #2538387)
#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;
int i = 0;
while ( i < lng )
{
if ( pat[j] == cuvant[i] )
{
i++;
j++;
}
if ( j == lg )
{
k++;
sol.push_back ( i - j );
j = v[lg-1];
if ( k == 1000 )
exit ( 0 );
}
else if ( i < lng && pat[j] != cuvant[i] )
{
if ( j )
j = v[j-1];
else
i++;
}
}
}
void preprocess ( )
{
int lng = pat.size();
v.reserve ( lng+1 );
v[0] = 0;
int j = 0;
for ( int i = 1; i < lng; i++ )
{
if ( pat[j] == pat[i] )
{
v[i] = j + 1;
j++;
}
else
{
while ( j && pat[j] != pat[i] )
j = v[j-1];
if ( pat[j] == pat[i] )
{
v[i] = j + 1 ;
j++;
}
else
v[i] = 0;
}
}
}
void read ( )
{
getline ( fin, pat );
getline ( fin, cuvant );
}