Pagini recente » Cod sursa (job #2169411) | Cod sursa (job #2656113) | Clasamentul arhivei de probleme | Cod sursa (job #1647242) | Cod sursa (job #2241903)
#include <iostream>
#include <fstream>
#include <vector>
const int nmax = 2000005;
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int n, m, v[nmax];
string A,B;
vector<int> rez;
void LPS(){
int i = 1, j = 0;
while(i < m){
if(A[i] == A[j]){
j++;
v[i] = j;
i++;
}
else{
if(j != 0)
j = v[j - 1];
else{
v[i] = 0;
i++;
}
}
}
}
void KMP(){
int i = 0,j = 0;
while(i < n){
if(B[i] == A[j]){
j++;
i++;
if(j == m){
rez.push_back(i - j);
j = v[j - 1];
}
}else{
if(j != 0)
j = v[j - 1];
else
i++;
}
}
}
int main()
{
fin >> A >> B;
n = B.size();
m = A.size();
LPS();
KMP();
fout << rez.size() <<endl;
for(unsigned int i = 0; i < rez.size() && i < 1000; i++)
fout<< rez[i] <<' ';
return 0;
}