Pagini recente » Cod sursa (job #769120) | Cod sursa (job #1553188) | Cod sursa (job #86121) | Cod sursa (job #1122373) | Cod sursa (job #919563)
Cod sursa(job #919563)
#include<fstream>
#include<string>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
string p,t;
int m,n,nr,urm[2000001], sol[2000001];
void ComputePrefix(string p)
{
int k = -1;
urm[0] = -1;
for ( int x = 1; x < m; x++ )
{
while ( k>-1 && p[k+1] != p[x] )
k = urm[k];
if (p[k+1] == p[x])
k++;
urm[x] = k;
}
}
int main()
{
int x= -1;
fin>> p >> t;
m = p.size(); n = t.size();
ComputePrefix(p);
for( int i = 0; i < n; i++ )
{
while ( x>-1 && p[x+1] != t[i] )
x = urm[x];
if ( p[x+1] == t[i] )
x++;
if(x==m-1)
{
nr++;
if ( nr <= 1000 )
sol[nr] = i-m+1;
x = urm[m-1];
}
}
fout << nr << '\n';
for ( int i = 1; i <= min(1000,nr); i++ )
fout << sol[i] << ' ';
fin.close();
fout.close();
}