Pagini recente » Cod sursa (job #263473) | Cod sursa (job #3127739) | Cod sursa (job #1682460) | Cod sursa (job #1507967) | Cod sursa (job #2721625)
#include<fstream>
#include<iostream>
#include<cstring>
#include<vector>
#define N 2000001
using namespace std;
char s[N],sir[N];
int prefix[N];
void calcul_prefix(char s[]){
int n=strlen(s),i,j;
int a[n][n];
prefix[0]=-1;
for(i=1;i<n;i++){
j=prefix[i-1];
if(s[i]==s[j+1])
prefix[i]=j+1;
else{
while(j>=0 && s[i]!=s[j+1])
j=prefix[j];
if(s[i]==s[j+1])
prefix[i]=j+1;
else
prefix[i]=-1; //=j
/*
if(s[i]==s[j+1])
j++;
prefix[i]=j;
*/
}
}
}
int main(){
ifstream f("strmatch.in");
ofstream g("strmatch.out");
f.getline(s,N);
f.getline(sir,N);
calcul_prefix(s);
int m=strlen(s);
int n=strlen(sir);
int i=0,j=-1,nr=0;
vector<int> poz;
while(i<n){
//cout<<j;
if(sir[i]==s[j+1]){
j++;
if(j+1==m){
nr++;
poz.push_back(i-m+1);
//j=-1;
}
i++;
}
else{
while(j>=0 && sir[i]!=s[j+1])
j=prefix[j];
if(j==-1)
i++;
}
}
g<<nr<<endl;
for(i=0;i<poz.size();i++)
g<<poz[i]<<" ";
g.close();
}