Pagini recente » Cod sursa (job #1722711) | Cod sursa (job #87690) | Cod sursa (job #219600) | Cod sursa (job #2200359) | Cod sursa (job #919351)
Cod sursa(job #919351)
#include <fstream>
#include <string>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
string p, t;
int urm[2000001], sol[2000001], n, m, nr;
void ComputePrefix(string p)
{
int k=-1;
urm[0]=0;
for ( int x = 1; x < m; x++ )
{
while(k > 0 && 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 > 0 && p[x+1] != t[i] )
x = urm[x];
if (p[x+1] == t[i]) x++;
if ( x == m-1)
sol[++nr] = i-m+1;
}
fout << nr << '\n';
for ( int i = 1; i<= min(nr,1000); i++ )
fout << sol[i] << ' ';
fin.close();
fout.close();
return 0;
}