Pagini recente » Cod sursa (job #230897) | Cod sursa (job #2768968) | Cod sursa (job #402400) | Cod sursa (job #762776) | Cod sursa (job #2432068)
#include <bits/stdc++.h>
#define nmax 2000005
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char a[nmax],b[nmax];
int pi[nmax] , n , m;
vector < int > V;
void make_prefix()
{
int k = 0;
pi[1] = 0;
///fout << 0 << " ";
for(int i = 2 ; i <= n; ++i)
{
while( k > 0 && a[ k + 1] != a[i] )
k = pi[k];
if( a[k+1] == a[i] )
++k;
pi[i] = k;
///fout << pi[i] << " ";
}
}
void KMP()
{
int k = 0;
for(int i = 1 ; i <= m ; ++i)
{
while( k > 0 && a[k+1] != b[i] )
k = pi[k];
if( a[k+1] == b[i] )
++k;
if( k == n )
{ k = pi[k];
V.push_back( i - n );
}
}
}
int main()
{
fin >> a + 1 ;
fin >> b + 1 ;
n = strlen(a + 1);
m = strlen(b + 1);
make_prefix();
KMP();
fout << V.size() << '\n';
for(int i = 0 ; i < min((int)V.size(),1000) ; ++i)
fout << V[i] << " ";
return 0;
}