Pagini recente » Cod sursa (job #3209581) | Cod sursa (job #1437485) | Cod sursa (job #947739) | Cod sursa (job #1255599) | Cod sursa (job #578366)
Cod sursa(job #578366)
#include <cstdio>
#include <string.h>
#include <vector>
using namespace std;
FILE *f,*g;
vector <int> v;
char s1[1000100],s2[1000100];
int urm[1000100];
int i,k,n,m;
void urmat() {
int i,k;
for (urm[0]=0,k=0,i=1;i<strlen(s1);i++) {
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);
while (! ( (s1[strlen(s1)-1]>='A' && s1[strlen(s1)-1]<='Z') || ( s1[strlen(s1)-1]>='a' && s1[strlen(s1)-1]<='z') ) )
s1[strlen(s1)-1]='\0';
while (! (s2[strlen(s2)-1]>='A' && s2[strlen(s2)-1]<='Z') || ((s2[strlen(s2)-1]>='a' && s2[strlen(s2)-1]<='z')))
s2[strlen(s2)-1]='\0';
urmat();
m=strlen(s1);
n=strlen(s2);
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);
}