Pagini recente » Cod sursa (job #2602982) | Borderou de evaluare (job #688506) | Cod sursa (job #3207996) | Borderou de evaluare (job #1002034) | Cod sursa (job #568350)
Cod sursa(job #568350)
#include<fstream>
#include<vector>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
string A, B;
int n, m;
int nr;
void KMP();
void Prefix();
void Write();
int main()
{
fin >> A;
fin >> B;
KMP();
fin.close();
fout.close();
return 0;
}
void KMP()
{
// prefix;
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;
}
//for( int i = 0; i <= A.size(); ++i )
// fout << T[i] << ' ';
//KMP;
vector<int> pozitii;
int sp = 0;
int kp = 0;
while( sp < B.size() )
{
while( kp != -1 && ( kp == A.size() || A[kp] != B[sp] ) )
kp = T[kp];
kp++;
sp++;
if( kp == A.size() )
pozitii.push_back( sp - kp );
}
fout << pozitii.size() << '\n';
int n = pozitii.size();
if ( n > 1000 )
n = 1000;
for( int i = 0; i < n; ++i )
fout << pozitii[i] << ' ';
}