Pagini recente » Cod sursa (job #817405) | Cod sursa (job #2357187) | Cod sursa (job #1784027) | Cod sursa (job #1091048) | Cod sursa (job #728873)
Cod sursa(job #728873)
#include <cstdio>
#include <string.h>
#include <vector>
using namespace std;
#define nm 2000010
vector <int> c;
FILE *f,*g;
char s1[nm],s2[nm];
int urm[nm],sol=0,m,i;
void pas1() {
int i,k;
s1[0]='0';
fscanf(f,"%s",s1+1);
for (urm[1]=0,k=0,i=2,m=strlen(s1)-1;i<=m;i++) {
while (k>0 && s1[k+1]!=s1[i]) k=urm[k];
if (s1[k+1]==s1[i]) k++;
urm[i]=k;
}
}
void pas2() {
int i,k,n;
s2[0]='0';
fscanf(f,"%s",s2+1);
for (k=0,n=strlen(s2)-1,i=1;i<=n;i++) {
while (k>0 && s1[k+1]!=s2[i]) k=urm[k];
if (s1[k+1]==s2[i]) k++;
if (k==m) {
sol++;
if (c.size()<1000)
c.push_back(i-m);
}
}
}
int main() {
f=fopen("strmatch.in","r");
g=fopen("strmatch.out","w");
pas1(); //creare urm
pas2(); //rezolvarea propriu-zisa
fprintf(g,"%d\n",sol);
for (i=0;i<c.size();i++)
fprintf(g,"%d ",c[i]);
fclose(g);
return 0;
}