Pagini recente » Cod sursa (job #730800) | Cod sursa (job #1348449) | Cod sursa (job #1236653) | Cod sursa (job #1308422) | Cod sursa (job #884644)
Cod sursa(job #884644)
#include<stdio.h>
#include<string.h>
#include<vector>
#define maxn 2000005
using namespace std;
char a[maxn],b[maxn];
int urm[maxn],m,n,nr;
vector <int> sol;
void cit(){
FILE *f;
f=fopen("strmatch.in","r");
fgets(a,maxn,f);
fgets(b,maxn,f);
fclose(f);
m=strlen(a);
n=strlen(b);
while((a[m-1]<'a'||a[m-1]>'z')&&(a[m-1]<'A'||a[m-1]>'Z')&&(a[m-1]<'0'||a[m-1]>'9'))
m--;
a[m]='\0';
while((b[n-1]<'a'||b[n-1]>'z')&&(b[n-1]<'A'||b[n-1]>'Z')&&(b[n-1]<'0'||b[n-1]>'9'))
n--;
b[n]='\0';
}
void urmatorul(){
int x,k;
urm[0]=-1;
k=-1;
for(x=1;x<m;x++){
while(k>=0&&a[x]!=a[k+1])
k=urm[k];
if(a[k+1]==a[x])
k++;
urm[x]=k;
}
}
void kmp(){
int i,k;
k=-1;
for(i=0;i<n;i++){
while(k>=0&&a[k+1]!=b[i])
k=urm[k];
if(a[k+1]==b[i])
k++;
if(k==m-1){
nr++;
if(nr<=1000)
sol.push_back(i-m+1);
k=urm[k];
}
}
}
void afis(){
FILE *f;
f=fopen("strmatch.out","w");
fprintf(f,"%d\n",nr);
for(int i=0;i<nr&&i<1000;i++)
fprintf(f,"%d ",sol[i]);
fclose(f);
}
int main(){
cit();
urmatorul();
kmp();
afis();
return 0;
}