Pagini recente » Cod sursa (job #2757572) | Cod sursa (job #3152280) | Cod sursa (job #2826688) | Cod sursa (job #2398232) | Cod sursa (job #407425)
Cod sursa(job #407425)
#include <string>
#include <vector>
#include <fstream>
using namespace std;
int main(){
ifstream in("strmatch.in");
ofstream out("strmatch.out");
string a,b;in>>a>>b;
vector<int> gasiri(1000);
int n=0;
vector<int> prefix (a.length(),0);
int k=-1;
for(int i=1;i<a.length();i++){
while(k>=0 and a[k+1]!=a[i]){
k=prefix[k];
}
if(a[k+1]==a[i]){
k++;
}
prefix[i]=k;
}
int q=-1;
for(int i=0;i<b.length();i++){
while(q>=0 and a[q+1]!=b[i]){
q=prefix[q];
}
if(a[q+1]==b[i]){
q++;
}
if(q+1==a.length()){
if(n<1000){
gasiri[n]=i-a.length()+1;
n++;
}
}
}
out<<n<<endl;
for(int i=0;i<n and i<1000;i++){
out<<gasiri[i]<<" ";
}
}