Pagini recente » Borderou de evaluare (job #1718084) | Cod sursa (job #2694903) | Borderou de evaluare (job #698506) | Borderou de evaluare (job #2053968) | Cod sursa (job #568609)
Cod sursa(job #568609)
#include<fstream>
#include<vector>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char A[2000001];
char B[2000001];
int t[2000001];
void KMP();
int main()
{
fin >> A+1;
fin >> B;
KMP();
fin.close();
fout.close();
return 0;
}
void KMP()
{
t[1] = 0;
int n = strlen(A+1);
int pos = 0;
for( int i = 2; i <= n; ++i )
{
while( pos > 0 && A[pos+1] != A[i] )
pos = t[pos];
if( A[pos+1] == A[i] )
pos++;
t[i] = pos;
}
//for( int i = 1; i <= n; ++i )
// fout << t[i] << ' ';
int m = strlen(B);
pos = 0;
vector<int> pozitii;
for( int i = 0; i < m; ++i )
{
while( pos > 0 && A[pos+1] != B[i] )
pos = t[pos];
if( A[pos+1] == B[i] )
pos++;
if( pos == n )
{
pos = t[pos];
pozitii.push_back(i-n+1);
}
}
int z = pozitii.size();
fout << z << '\n';
if( z > 1000 )
z = 1000;
for( int i = 0; i < z; ++i )
fout << pozitii[i] << ' ';
}