Pagini recente » Cod sursa (job #2428784) | Cod sursa (job #302821) | Cod sursa (job #2889833) | Cod sursa (job #1241158) | Cod sursa (job #758453)
Cod sursa(job #758453)
#include <cstdio>
#include <iostream>
#include <fstream>
#include <list>
#include <limits.h>
#include <stdio.h>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <stdio.h>
#include <algorithm>
#include <deque>
#include <string.h>
#include <string>
#define NMAX 2000002
using namespace std;
int state;
int T1[NMAX];
int T2[NMAX];
char s1[NMAX],s2[NMAX];
vector<int> secv;
void match(char* s1, char* s2, int *T1, int *T2)
{
int m = 0;
int i = 0;
int l1 = strlen(s1)-1;
int l2 = strlen(s2)-1;
while ((m+i)<=l2-1)
{
if (s1[i] ==s2[m+i])
{
if (i==l1-1){
secv.push_back(m);
m = m+i-T1[i];
if (T1[i]>0)
i = T1[i];
else i=0;
}
else {
i++;
}
}
else{
m = m+i- T1[i];
if (T1[i]>0)
i = T1[i];
else i=0;
}
}
}
void buildT(char* s,int *T)
{
int l = strlen(s1)-1;
T[0] = -1;T[1] = 0;
int pos = 0;
int i = 2;
while (i<l)
{
char c = s[i-1];
char c2= s[pos];
if (c == c2)
{
pos++; T[i] =pos;i++;
}
else if (pos>0){
pos = T[pos];
}
else
{
T[i] = 0;
i++;
}
}
}
int main()
{
FILE* f = fopen("strmatch.in","r");
FILE* g = fopen("strmatch.out","w+");
fgets(s1,NMAX,f);
fgets(s2,NMAX,f);
buildT(s2,T2);
buildT(s1,T1);
match(s1,s2,T1,T2);
fprintf(g,"%d\n",secv.size());
int nr = secv.size();
if (nr>1000) nr = 1000;
for (int i=0;i<nr;i++)
fprintf(g,"%d ",secv[i]);
fprintf(g,"\n");
fclose(f);
fclose(g);
return 0;
}