Pagini recente » Cod sursa (job #2172960) | Cod sursa (job #1240747) | Cod sursa (job #2360066) | Cod sursa (job #1269074) | Cod sursa (job #2753370)
#include <fstream>
#include <cstring>
#include <vector>
#define K 2000002
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int prefix[K],n,m,i,j,x;
char a[K],b[K];
vector <int> sol;
int main(){
fin>>a>>b;
n=strlen(a);
m=strlen(b);
prefix[0]=0;
//prefix[i]=lungimea celui mai lung prefix propriu care e si sufix in sirul s[0,..,i]
for(i=1;i<n;i++){
j=prefix[i-1];
while(j>0 && a[i]!=a[j])
j=prefix[j-1];
if(a[i]==a[j])
j++;
prefix[i]=j;
}
int j=0;
for(int i=0;i<m;i++){
while(j>0 && b[i]!=a[j])
j=prefix[j-1];
if(b[i]==a[j])
j++;
if(j==n){
j=prefix[j-1];
sol.push_back(i-n+1);
}
}
fout<<sol.size()<<"\n";
for(int i=0;i<sol.size() && i<1000;i++)
fout<<sol[i]<<" ";
return 0;
}