Pagini recente » Cod sursa (job #3187507) | Cod sursa (job #2330097) | Cod sursa (job #1041801) | Cod sursa (job #463273) | Cod sursa (job #578404)
Cod sursa(job #578404)
#include <cstdio>
#include <string.h>
#include <vector>
using namespace std;
FILE *f,*g;
vector <int> v;
char s1[2000100],s2[2000100];
int urm[2000100];
int i,k,n,m;
void urmat() {
int i,k;
for (urm[0]=0,i=1;i<m;i++) {
k=urm[i-1];
while (k>0 && s1[k]!=s1[i])
k=urm[k-1];
if (s1[i]==s1[k]) k++;
urm[i]=k;
}
}
int main () {
f=fopen("strmatch.in","r");
g=fopen("strmatch.out","w");
fgets(s1,2000100,f);
fgets(s2,2000100,f);
fclose(f);
s1[strlen(s1)-1]='\0';
m=strlen(s1);
n=strlen(s2);
urmat();
k=0;
for (i=0;i<n;i++) {
while (k>0 && s1[k]!=s2[i])
k=urm[k-1];
if (s1[k]==s2[i])
k++;
if (k==strlen(s1)) {
if (v.size()<1000)
v.push_back(i-m+1);
k=urm[k-1];
}
}
fprintf(g,"%d\n",v.size());
for (vector<int>::iterator j=v.begin();j<v.end();j++) {
fprintf(g,"%d ",*j);
}
fclose(g);
return 0;
}