Cod sursa(job #758446)

Utilizator iris88Nagy Aliz iris88 Data 15 iunie 2012 18:08:47
Problema Potrivirea sirurilor Scor 38
Compilator cpp Status done
Runda Arhiva educationala Marime 1.46 kb
#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 2000001
using namespace std;
int state;

int T1[NMAX];
int T2[NMAX];
char s1[NMAX],s2[NMAX];
vector<int> secv;
void match(string s1, string s2, int *T1, int *T2)
{
	int m = 0;
	int i = 0;
	int l1 = s1.length()-1;
	int l2 = s2.length()-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(string s,int *T)
{
	int l = s.length();
	T[0] = -1;T[1] = 0;
	int pos = 0;
	int i = 2;
	while (i<l)
	{
		char c = s.at(i-1); 
		char c2= s.at(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());
	for (int i=0;i<secv.size();i++)
		fprintf(g,"%d ",secv[i]);
	fprintf(g,"\n");
	fclose(f);
	fclose(g);
}