Pagini recente » Cod sursa (job #2655760) | Cod sursa (job #2578210) | Cod sursa (job #2625244) | Cod sursa (job #241355) | Cod sursa (job #3243805)
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
using namespace std;
ifstream input("strmatch.in");
ofstream output("strmatch.out");
int main()
{
string a, b;
input>>a>>b;
vector<int>T(a.size() + 1, 0);
int k=0;
for(int i=1;i<a.size();i++){
while(k>0&&a[k]!=a[i]){
k=T[k];
}
if(a[k]==a[i]){
k++;
}
T[i]=k;
}
k=0;
int nr=0;
vector<int>pos;
for(int i=0;i<b.size();i++){
while(k>0&&a[k]!=b[i]){
k=T[k];
}
if(a[k]==b[i]){
k++;
}
if(k==a.size()){
if(nr<1000) {
pos.push_back(i-a.size()+1);
}
nr++;
k=T[k-1];
}
}
output<<nr<<endl;
int limit=min(nr,1000);
for(int i=0;i<limit;i++){
output<<pos[i]<<" ";
}
return 0;
}