Pagini recente » Cod sursa (job #1119903) | Cod sursa (job #2891227) | Cod sursa (job #1483737) | Cod sursa (job #909803) | Cod sursa (job #568352)
Cod sursa(job #568352)
#include<fstream>
#include<vector>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
string A;
string B;
void KMP();
int main()
{
fin >> A;
fin >> B;
KMP();
fin.close();
fout.close();
return 0;
}
void KMP()
{
vector<int> T( A.size() + 1, -1 );
for( int i = 1; i <= A.size(); ++i )
{
int pos = T[i-1];
while( pos != -1 && A[pos] != A[i-1] )
pos = T[pos];
T[i] = pos + 1;
}
vector<int> pozitii;
int ap = 0;
int bp = 0;
while( bp < B.size() )
{
while( ap != -1 && ( ap == A.size() || A[ap] != B[bp] ) )
ap = T[ap];
ap++;
bp++;
if( ap == A.size() )
pozitii.push_back( bp - ap );
}
fout << pozitii.size() << '\n';
int n = pozitii.size();
if( n > 1000 )
n = 1000;
for( int i = 0; i < n; ++i )
fout << pozitii[i] << ' ';
}