Pagini recente » Cod sursa (job #553587) | Cod sursa (job #1758749) | Cod sursa (job #1799654) | Cod sursa (job #2008942) | Cod sursa (job #2313568)
#include <iostream>
#include <fstream>
#include <string>
#include <algorithm>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
istream & in = fin;
ostream & out = fout;
string pat, tgt;
int pre[2000041];
int numba = 0;
int numbas[1041];
void Read()
{
getline(in, pat);
getline(in, tgt);
}
void CalcPre()
{
int i = 1, j = 0;
while(i < pat.size()){
if(pat[i] == pat[j]){
pre[i] = j+1;
i++;j++;
}else{
if(j != 0){
j = pre[j-1];
}else{
pre[i] = 0;
i++;
}
}
}
}
void KMP()
{
int i = 0, j = 0;
while(i < tgt.size()){
while(j != 0 && tgt[i] != pat[j]){
j = pre[j-1];
}
if(tgt[i] == pat[j]){
j++;
}
i++;
if(j == pat.size()){
j = pre[j-1];
if(numba < 1000){
numbas[numba] = i-pat.size();
}
numba++;
}
}
}
void Solve()
{
CalcPre();
KMP();
}
void Write()
{
out << numba << "\n";
numba = min(numba, 1000);
for(int i = 0; i < numba; i++){
out << numbas[i] << " ";
}
}
int main()
{
Read();
Solve();
Write();
return 0;
}