[C] Confrontare due stringhe quasi identiche

Linguaggi di programmazione: php, perl, python, C, bash e tutti gli altri.
zangetsu94
Prode Principiante
Messaggi: 137
Iscrizione: mercoledì 26 novembre 2014, 15:17
Desktop: Cinnamon
Distribuzione: Linux Mint 19.1 Tessa
Sesso: Maschile
Località: Torino

[C] Confrontare due stringhe quasi identiche

Messaggio da zangetsu94 »

Se ho delle sequenze di stringhe come la seguente:

ATCGTTAATTATTGGGATTCGCTTAGCATTGGGATTACTTAGCTTAGCTTA
ATCGTTAATTGCTTAGCTTAGCTTAGCTTAGCTTAGCTTAGCTTAGCTTA
ATCGTTAATTGCTTAGCTTAATTGGGATCCATCGGCTTAATCGGTCTTAA

Come posso controllare se una stringa più piccola è contenuta nella riga i-esima con un numero massimo N di caratteri differenti? (Ovviamente il primo o l'ultimo carattere devono essere identici).

Ad esempio:

Stringa da confrontare: ATTGGGATTA

ATCGTTAATTATTGGGATTCGCTTAGCATTGGGATTACTTAGCTTAGCTTA
ATCGTTAATTGCTTAGCTTAGCTTAGCTTAGCTTAGCTTAGCTTAGCTTA
ATCGTTAATTGCTTAGCTTAATTGGGATCCATCGGCTTAATCGGTCTTAA

Trovato nella sequenza 1 in posizione 11 con 1 mismatch.
Trovato nella sequenza 1 in posizione 28 con 0 mismatch.
Trovato nella sequenza 3 in posizione 21 con 2 mismatch.

Grazie in anticipo :birra:
PC: Asus F555UJ-DM059T CPU: Intel Core i7-6500U OS: Linux Mint KDE 18.3 RAM: 8GB GPU: nVidia GeForce-920M
Avatar utente
M_A_W_ 1968
Scoppiettante Seguace
Scoppiettante Seguace
Messaggi: 856
Iscrizione: venerdì 15 febbraio 2013, 3:57
Desktop: KDE
Distribuzione: SuSE
Sesso: Maschile
Località: Un luogo geometrico
Contatti:

Re: [C] Confrontare due stringhe quasi identiche

Messaggio da M_A_W_ 1968 »

Per ottenere un risultato pseudo-fuzzy, la via più breve è inventare un modo per mettere insieme un buon algoritmo di pattern matching (uno a scelta tra Rabin-Karp, Knuth-Morris-Pratt, Boyer-Moore, Baeza–Yates–Gonnet, Sunday... in questo caso solo Horspool sarebbe decisamente poco adatto a priori, e scarterei anche i vari DFA espliciti) e il concetto di distanza di Levenshtein, o distanza di edit, una utilissima misura di natura operazionale che ti fornisce, in questo caso, esattamente la differenza in caratteri tra due stringhe di pari lunghezza.

Per il momento studia bene gli algoritmi indicati e cerca di familiarizzare con la distanza di edit, provando a buttare giù qualcosa. Poi vediamo.
Sì, un blog ce l'ho perfino io: gli è che mi manca il tempo...

"...in una società che sembra sempre più spaventata dai problemi troppo articolati e che rigetta come un corpo estraneo ogni elemento di complessità, sapremo ancora come utilizzare il parere degli esperti?"
zangetsu94
Prode Principiante
Messaggi: 137
Iscrizione: mercoledì 26 novembre 2014, 15:17
Desktop: Cinnamon
Distribuzione: Linux Mint 19.1 Tessa
Sesso: Maschile
Località: Torino

Re: [C] Confrontare due stringhe quasi identiche

Messaggio da zangetsu94 »

Qualcosa mi dice che non passerò l'esame di domani :nono: tra tutti gli algoritmi e i concetti elencati non ce n'è uno che io abbia mai sentito nominare, non per mia negligenza ma piuttosto perché il mio corso (programmazione C da 8 crediti, 40 lezioni da un'ora e mezza...) semplicemente non lo prevede...poi all'esame ti ritrovi robe del genere :muro: :muro: :muro:
PC: Asus F555UJ-DM059T CPU: Intel Core i7-6500U OS: Linux Mint KDE 18.3 RAM: 8GB GPU: nVidia GeForce-920M
Avatar utente
vaeVictis
Imperturbabile Insigne
Imperturbabile Insigne
Messaggi: 4703
Iscrizione: venerdì 27 luglio 2012, 17:58
Desktop: Gnome
Distribuzione: Ubuntu 20.04 64bit

Re: [C] Confrontare due stringhe quasi identiche

Messaggio da vaeVictis »

Le soluzioni proposte dal buon M_A_W riguardano il "meglio" che puoi trovare, nel senso che non so se per il tuo corso ti è richiesta una conoscenza del genere.
Non è che ti stai complicando la vita? Magari vogliono semplicemente che gli imposti un algoritmo "cretino" :)
Pirates arrrrrrrrrrr awesome!!!
«I fear not the man who has practiced 10000 kicks once,
but I fear the man who has practiced one kick 10000 times.»
Avatar utente
Vincenzo1968
Scoppiettante Seguace
Scoppiettante Seguace
Messaggi: 450
Iscrizione: lunedì 14 gennaio 2013, 14:21
Desktop: Unity
Distribuzione: Ubuntu 18.04.3 LTS x86_64
Località: Villabate(PA)
Contatti:

Re: [C] Confrontare due stringhe quasi identiche

Messaggio da Vincenzo1968 »

Potresti adattare questo codice che ho sviluppato una volta per partecipare a un contest:

Codice: Seleziona tutto

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <malloc.h>
#include <time.h>

#define FILE1 "../Files/DNA1.txt"
#define FILE2 "../Files/DNA2.txt"

#define BUFFER_SIZE 4096
#define MAX_STACK 100
#define PREFIX_SIZE 8

typedef struct tagRisultato
{
	int pos1;
	int pos2;
	char p1[1024];
	char p2[1024];
	int len;
} Risultato;

typedef struct tagLista
{
	int pos;
	struct tagLista* next;
} Lista;

typedef struct tagTree
{
	char key[PREFIX_SIZE + 1];
	Lista *pLista;
	struct tagTree *left;
	struct tagTree *right;
} Tree;

Lista* ListNewNode(int val);
Lista* ListAppend(Lista* first, int val);
void ListFree(Lista* first);

Tree *TreeNewNode(char *pKey, int pos);
Tree *TreeInsertNode(Tree *node, char * pKey, int pos);
void TreeSearch(Tree *head, Tree **result, char *pKey);
void TreeFree(Tree *head);

Lista* ListNewNode(int val)
{
	Lista *n;

	n = (Lista *)malloc(sizeof(Lista));

	if( n == NULL )
		return NULL;

	n->pos = val;
	n->next = NULL;

	return n;
}

Lista* ListAppend(Lista* first, int val)
{
	Lista *n = first, *nuovo;

	if ( first == NULL )
		return ListNewNode(val);

	n = first;
	while( n->next != NULL )
	{
		n = n->next;
	}

	nuovo = ListNewNode(val);
	n->next = nuovo;

	return first;
}

void ListFree(Lista* first)
{
	Lista *n1 = first, *n2;
	while ( n1 != NULL )
	{
		n2 = n1->next;
		free(n1);
		n1 = n2;
	}
}

Tree *TreeNewNode(char *pKey, int pos)
{
	Tree *r;
	Lista *l;

	r = (Tree *) malloc(sizeof(Tree));
	if(!r)
	{
		printf("Memoria insufficiente.\n");
		return NULL;
	}

	l = (Lista *) malloc(sizeof(Lista));
	if(!l)
	{
		printf("Memoria insufficiente.\n");
		return NULL;
	}
	l->pos = pos;
	l->next = NULL;
	

	strcpy(r->key, pKey);
	r->pLista = l;
	r->left = NULL;
	r->right = NULL;

	return r;
}

Tree *TreeInsertNode(Tree *node, char * pKey, int pos)
{
	int res;
	Tree *pRadice = NULL;

	if( !node )
	{
		node = TreeNewNode(pKey, pos);
		return node;
	}

	pRadice = node;
	
	while( 1 )
	{
		res = strcmp(pKey, node->key);
		if ( res < 0 )
		{
			if ( !node->left )
			{
				node->left = TreeNewNode(pKey, pos);
				break;
			}
			node = node->left;
		}
		else if ( res > 0 )
		{
			if ( !node->right )
			{
				node->right = TreeNewNode(pKey, pos);
				break;
			}
			node = node->right;
		}
		else
		{
			node->pLista = ListAppend(node->pLista, pos);
			break;
		}

	}

	node = pRadice;

	return node;
}

void TreeSearch(Tree *head, Tree **result, char *pKey)
{
	int res;
	Tree *node;

	*result = NULL;
	node = head;

	if ( !head )
		return;

	while( 1 )
	{
		res = strcmp(pKey, node->key);
		if ( res < 0 )
		{
			if ( !node->left )
				break;
			node = node->left;
		}
		else if ( res > 0 )
		{
			if ( !node->right )
				break;
			node = node->right;
		}
		else /* key == node->data */
		{
			*result = node;
			break;
		}
	}
}

void TreeFree(Tree *head)
{
	Tree *temp1, *temp2;

	Tree *stack[MAX_STACK];
	int top;

	top = 0;
 
	if ( !head )
		return;

	temp1 = temp2 = head;

	while ( temp1 != NULL )
	{
		for(; temp1->left != NULL; temp1 = temp1->left)
			stack[top++] = temp1;

		while ( (temp1 != NULL) && (temp1->right == NULL || temp1->right == temp2) )
		{
			temp2 = temp1;
			ListFree(temp2->pLista);
			free(temp2);
			if ( top == 0 )
				return;
			temp1 = stack[--top];
		}

		stack[top++] = temp1;
		temp1 = temp1->right;
	}
}

int LeggiDimensioniFile(char *szFileName)
{
	FILE *fp;
	long k;

	fp = fopen(szFileName, "rb");

	if ( fp == NULL )
		return 0;

	if ( fseek(fp, 0, SEEK_END) )
	{
		fclose(fp);
		return 0;
	}

	k = ftell(fp);

	fclose(fp);

	return k;
}

int LeggiStringa(char *szFileName, char *buffer, int dimFile)
{
	FILE *fp;

	fp = fopen(szFileName, "r");

	if ( fp == NULL )
		return 0;

	if ( fgets(buffer, dimFile+1, fp) == NULL )
	{
		printf("\nErrore nella lettura del file %s\n", szFileName);
		fclose(fp);
		return 0;
	}
	*(buffer + dimFile) = '\0';

	fclose(fp);

	return dimFile;
}

void Trova(char *szNomeFile1, char *szNomeFile2, Risultato *pRisultato)
{
	Tree *pTree;
	Tree *pNode;
	Lista *pLista;
	int p1_len, p2_len;
	int k;
	int len, len_prec;
	int numErrors;
	int bTrovato;
	int MaxPrefix;

	int x;

	char strSearch[1024] = "";

	char strRes[1024] = "";
	char strTemp1[1024] = "";
	char strTemp2[1024] = "";	

	int pos1, pos2;
	int pos1x, pos2x;

	int post2;

	char *p1 = NULL;
	char *p2 = NULL;
	
	len = 0;
	pos1x = pos2x = 0;

	p1_len = LeggiDimensioniFile(szNomeFile1);
	p2_len = LeggiDimensioniFile(szNomeFile2);

	p1 = (char*)malloc(sizeof(char)*p1_len + 1);
	if ( !p1 )
	{
		printf("Errore nell'allocazione della memoria.");
		return;
	}
	p1[0] = '\0';

	p2 = (char*)malloc(sizeof(char)*p2_len + 1);
	if ( !p2 )
	{
		printf("Errore nell'allocazione della memoria.");
		return;
	}
	p2[0] = '\0';

	if ( !LeggiStringa(szNomeFile1, p1, p1_len) )
		return;

	if ( !LeggiStringa(szNomeFile2, p2, p2_len) )
		return;

	if ( PREFIX_SIZE < p2_len )
		MaxPrefix = PREFIX_SIZE;
	else
		MaxPrefix = p2_len;

	if ( p1_len < PREFIX_SIZE )
	{
		pRisultato->len = len;
		pRisultato->pos1 = pos1x;
		pRisultato->pos2 = pos2x;
		strcpy(pRisultato->p1, strTemp1);
		strcpy(pRisultato->p2, strTemp2);

		free(p1);
		free(p2);

		return;
	}
	
	for ( x = MaxPrefix; x > 0; x--)
	{
		pTree = NULL;
		pos1 = 0;
		while ( pos1 < p1_len - x )
		{
			memcpy(strSearch, p1 + pos1, x);
			*(strSearch + x) = '\0';

			pTree = TreeInsertNode(pTree, strSearch, pos1);

			pos1++;
		}

		pos1 = 0;
		pos2 = 0;
		strTemp1[0] = '\0';
		strTemp2[0] = '\0';
		strSearch[0] = '\0';
		pLista = NULL;
		pNode = NULL;
		len = 0;
		len_prec = 0;
		numErrors = 0;
		bTrovato = 0;

		while ( pos2 < p2_len - x )
		{
			memcpy(strSearch, p2 + pos2, x);
			*(strSearch + x) = '\0';

			TreeSearch(pTree, &pNode, strSearch);
			if ( pNode != NULL )
			{
				pLista = pNode->pLista;

				while ( pLista != NULL )
				{
					pos1 = pLista->pos;
					numErrors = 0;
					k = x;
					post2 = pos2;
					if ( pos2 > x && pos1 > x )
					{
						k = 0;
						while ( (*(p2 + pos2) == *(p1 + pos1)) || (numErrors < 2) )
						{
							if ( *(p2 + pos2) != *(p1 + pos1) )
								numErrors++;
							pos1--;
							pos2--;
							if ( pos2 < 0 || pos1 < 0 )
								break;
						}
						pos1 += 1;
						pos2 += 1;
						numErrors = 0;
					}
					while ( (*(p2 + pos2 + k) == *(p1 + pos1 + k)) || (numErrors < 2) )
					{
						if ( *(p2 + pos2 + k) != *(p1 + pos1 + k) )
							numErrors++;
						k++;
					}
					if ( k > len_prec )
					{
						len = k;
						pos1x = pos1;
						pos2x = pos2;
						len_prec = len;

						bTrovato = 1;
					}
					pos2 = post2;
					pLista = pLista->next;
				}
			}

			pos2++;
		}
		TreeFree(pTree);
		if ( bTrovato )
			break;
	}

	pos1 = pos1x;
	pos2 = pos2x;
	len_prec = len;
	numErrors = 0;
	while ( (*(p1 + pos1) == *(p2 + pos2)) || (numErrors < 2) )
	{
		if ( *(p2 + pos2) != *(p1 + pos1) )
			numErrors++;
		pos2++;
		pos1++;
		if ( numErrors == 2 )
			break;
	}
	len = 0;
	numErrors = 0;
	while ( (*(p1 + pos1 + len) == *(p2 + pos2 + len)) || (numErrors < 2) )
	{
		if ( *(p2 + pos2 + len) != *(p1 + pos1 + len) )
			numErrors++;
		len++;
	}
	if ( len_prec < len )
	{
		pos1x = pos1;
		pos2x = pos2;
	}
	else
	{
		len = len_prec;
	}

	memcpy(strTemp1, p1 + pos1x, len);
	*(strTemp1 + len) = '\0';

	memcpy(strTemp2, p2 + pos2x, len);
	*(strTemp2 + len) = '\0';

	sprintf(strRes,
			"\nStringhe\n\n%s\n%s\n\ndi lunghezza %d trovate alle posizioni %d e %d\n",
			strTemp1,
			strTemp2,
			len,
			pos1x,
			pos2x);

	pRisultato->len = len;
	pRisultato->pos1 = pos1x;
	pRisultato->pos2 = pos2x;
	strcpy(pRisultato->p1, strTemp1);
	strcpy(pRisultato->p2, strTemp2);

	x = len_prec + 1;

	pos1 = 0;
	pos2 = pos2x + 1;
	strTemp1[0] = '\0';
	strSearch[0] = '\0';
	len_prec = len;
	len = 0;
	numErrors = 0;

	memcpy(strSearch, p2 + pos2, x);
	*(strSearch + x) = '\0';

	k = 0;
	while ( *(p1 + k) != *(p2 + k) )
		k++;
	pos1 = k;

	while ( pos1 < p1_len - x )
	{	
		memcpy(strTemp1, p1 + pos1, x);
		*(strTemp1 + x) = '\0';

		k = 0;
		while ( k < x )
		{
			if ( *(strSearch + k) != *(strTemp1 + k) )
				numErrors++;
			if ( numErrors > 2 )
				break;
			k++;
		}
		if ( k >= x && len_prec > len )
		{
			len = k;
			pos1x = pos1;
			pos2x = pos2;
			len_prec = len;

			memcpy(strTemp1, p1 + pos1x, len);
			*(strTemp1 + len) = '\0';

			memcpy(strTemp2, p2 + pos2x, len);
			*(strTemp2 + len) = '\0';

			sprintf(strRes,
					"\nStringhe\n\n%s\n%s\n\ndi lunghezza %d trovate alle posizioni %d e %d\n",
					strTemp1,
					strTemp2,
					len,
					pos1x,
					pos2x);

			pRisultato->len = len;
			pRisultato->pos1 = pos1x;
			pRisultato->pos2 = pos2x;
			strcpy(pRisultato->p1, strTemp1);
			strcpy(pRisultato->p2, strTemp2);

			break;
		}

		pos1++;
	}

	free(p1);
	free(p2);
}

/*
gcc -Wall -Wextra -pedantic -O2 Contest04BParz.c -o c04
*/

int main()
{
	Risultato ris;
	char strTempo[512];
	char strRes[1024];
	
	clock_t c_start, c_end;
	
	c_start = clock();

	Trova(FILE1, FILE2, &ris);
	
	c_end = clock();

	sprintf(strRes,
			"\nStringhe\n\n%s\n%s\n\ndi lunghezza %d trovate alle posizioni %d e %d\n",
			ris.p1,
			ris.p2,
			ris.len,
			ris.pos1,
			ris.pos2);

	printf(strRes);

	sprintf(strTempo, "\nTempo impiegato -> %5.5f secondi\n", (double)(c_end - c_start) / CLOCKS_PER_SEC);

	printf(strTempo);

	return 0;
}
Output:

Codice: Seleziona tutto

[vincenzo]$ gcc -Wall -Wextra -pedantic -O2 Contest04BParz.c -o c04
[vincenzo]$ ./c04

Stringhe

ACTGTCCTGAAGATCGCTTGGCATCTCCG
ACTGTCCTGCAGATCGCTTTGCATCTCCG

di lunghezza 29 trovate alle posizioni 50002 e 70002

Tempo impiegato -> 0.07040 secondi
In pratica leggiamo due file, DNA1.txt(100058 caratteri) e DNA2.txt(80058 caratteri) contenenti, ciascuno, una lunga sequenza di DNA.
Il programma trova la più lunga sottostringa comune che differisce, al più, per due caratteri.

Qui puoi scaricare i due file per la prova:

http://wikisend.com/download/618392/DNA.tar.gz
È ormai difficile incontrare un cretino che non sia intelligente e un intelligente che non sia un cretino. [...] Oh i bei cretini di una volta! Genuini, integrali. Come il pane di casa. Come l'olio e il vino dei contadini. (da "Nero su nero" di Leonardo Sciascia)
zangetsu94
Prode Principiante
Messaggi: 137
Iscrizione: mercoledì 26 novembre 2014, 15:17
Desktop: Cinnamon
Distribuzione: Linux Mint 19.1 Tessa
Sesso: Maschile
Località: Torino

Re: [C] Confrontare due stringhe quasi identiche

Messaggio da zangetsu94 »

vaeVictis [url=http://forum.ubuntu-it.org/viewtopic.php?p=4772133#p4772133][img]http://forum.ubuntu-it.org/images/icons/icona-cita.gif[/img][/url] ha scritto:Le soluzioni proposte dal buon M_A_W riguardano il "meglio" che puoi trovare, nel senso che non so se per il tuo corso ti è richiesta una conoscenza del genere.
Non è che ti stai complicando la vita? Magari vogliono semplicemente che gli imposti un algoritmo "cretino" :)
Purtroppo l'algoritmo deve soddisfare la traccia che viene assegnata all'esame...Quell'algoritmo fa parte di un tema d'esame passato. :botta:
Vincenzo1968 [url=http://forum.ubuntu-it.org/viewtopic.php?p=4772138#p4772138][img]http://forum.ubuntu-it.org/images/icons/icona-cita.gif[/img][/url] ha scritto:Potresti adattare questo codice che ho sviluppato una volta per partecipare a un contest:

Codice: Seleziona tutto

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <malloc.h>
#include <time.h>

#define FILE1 "../Files/DNA1.txt"
#define FILE2 "../Files/DNA2.txt"

#define BUFFER_SIZE 4096
#define MAX_STACK 100
#define PREFIX_SIZE 8

typedef struct tagRisultato
{
	int pos1;
	int pos2;
	char p1[1024];
	char p2[1024];
	int len;
} Risultato;

typedef struct tagLista
{
	int pos;
	struct tagLista* next;
} Lista;

typedef struct tagTree
{
	char key[PREFIX_SIZE + 1];
	Lista *pLista;
	struct tagTree *left;
	struct tagTree *right;
} Tree;

Lista* ListNewNode(int val);
Lista* ListAppend(Lista* first, int val);
void ListFree(Lista* first);

Tree *TreeNewNode(char *pKey, int pos);
Tree *TreeInsertNode(Tree *node, char * pKey, int pos);
void TreeSearch(Tree *head, Tree **result, char *pKey);
void TreeFree(Tree *head);

Lista* ListNewNode(int val)
{
	Lista *n;

	n = (Lista *)malloc(sizeof(Lista));

	if( n == NULL )
		return NULL;

	n->pos = val;
	n->next = NULL;

	return n;
}

Lista* ListAppend(Lista* first, int val)
{
	Lista *n = first, *nuovo;

	if ( first == NULL )
		return ListNewNode(val);

	n = first;
	while( n->next != NULL )
	{
		n = n->next;
	}

	nuovo = ListNewNode(val);
	n->next = nuovo;

	return first;
}

void ListFree(Lista* first)
{
	Lista *n1 = first, *n2;
	while ( n1 != NULL )
	{
		n2 = n1->next;
		free(n1);
		n1 = n2;
	}
}

Tree *TreeNewNode(char *pKey, int pos)
{
	Tree *r;
	Lista *l;

	r = (Tree *) malloc(sizeof(Tree));
	if(!r)
	{
		printf("Memoria insufficiente.\n");
		return NULL;
	}

	l = (Lista *) malloc(sizeof(Lista));
	if(!l)
	{
		printf("Memoria insufficiente.\n");
		return NULL;
	}
	l->pos = pos;
	l->next = NULL;
	

	strcpy(r->key, pKey);
	r->pLista = l;
	r->left = NULL;
	r->right = NULL;

	return r;
}

Tree *TreeInsertNode(Tree *node, char * pKey, int pos)
{
	int res;
	Tree *pRadice = NULL;

	if( !node )
	{
		node = TreeNewNode(pKey, pos);
		return node;
	}

	pRadice = node;
	
	while( 1 )
	{
		res = strcmp(pKey, node->key);
		if ( res < 0 )
		{
			if ( !node->left )
			{
				node->left = TreeNewNode(pKey, pos);
				break;
			}
			node = node->left;
		}
		else if ( res > 0 )
		{
			if ( !node->right )
			{
				node->right = TreeNewNode(pKey, pos);
				break;
			}
			node = node->right;
		}
		else
		{
			node->pLista = ListAppend(node->pLista, pos);
			break;
		}

	}

	node = pRadice;

	return node;
}

void TreeSearch(Tree *head, Tree **result, char *pKey)
{
	int res;
	Tree *node;

	*result = NULL;
	node = head;

	if ( !head )
		return;

	while( 1 )
	{
		res = strcmp(pKey, node->key);
		if ( res < 0 )
		{
			if ( !node->left )
				break;
			node = node->left;
		}
		else if ( res > 0 )
		{
			if ( !node->right )
				break;
			node = node->right;
		}
		else /* key == node->data */
		{
			*result = node;
			break;
		}
	}
}

void TreeFree(Tree *head)
{
	Tree *temp1, *temp2;

	Tree *stack[MAX_STACK];
	int top;

	top = 0;
 
	if ( !head )
		return;

	temp1 = temp2 = head;

	while ( temp1 != NULL )
	{
		for(; temp1->left != NULL; temp1 = temp1->left)
			stack[top++] = temp1;

		while ( (temp1 != NULL) && (temp1->right == NULL || temp1->right == temp2) )
		{
			temp2 = temp1;
			ListFree(temp2->pLista);
			free(temp2);
			if ( top == 0 )
				return;
			temp1 = stack[--top];
		}

		stack[top++] = temp1;
		temp1 = temp1->right;
	}
}

int LeggiDimensioniFile(char *szFileName)
{
	FILE *fp;
	long k;

	fp = fopen(szFileName, "rb");

	if ( fp == NULL )
		return 0;

	if ( fseek(fp, 0, SEEK_END) )
	{
		fclose(fp);
		return 0;
	}

	k = ftell(fp);

	fclose(fp);

	return k;
}

int LeggiStringa(char *szFileName, char *buffer, int dimFile)
{
	FILE *fp;

	fp = fopen(szFileName, "r");

	if ( fp == NULL )
		return 0;

	if ( fgets(buffer, dimFile+1, fp) == NULL )
	{
		printf("\nErrore nella lettura del file %s\n", szFileName);
		fclose(fp);
		return 0;
	}
	*(buffer + dimFile) = '\0';

	fclose(fp);

	return dimFile;
}

void Trova(char *szNomeFile1, char *szNomeFile2, Risultato *pRisultato)
{
	Tree *pTree;
	Tree *pNode;
	Lista *pLista;
	int p1_len, p2_len;
	int k;
	int len, len_prec;
	int numErrors;
	int bTrovato;
	int MaxPrefix;

	int x;

	char strSearch[1024] = "";

	char strRes[1024] = "";
	char strTemp1[1024] = "";
	char strTemp2[1024] = "";	

	int pos1, pos2;
	int pos1x, pos2x;

	int post2;

	char *p1 = NULL;
	char *p2 = NULL;
	
	len = 0;
	pos1x = pos2x = 0;

	p1_len = LeggiDimensioniFile(szNomeFile1);
	p2_len = LeggiDimensioniFile(szNomeFile2);

	p1 = (char*)malloc(sizeof(char)*p1_len + 1);
	if ( !p1 )
	{
		printf("Errore nell'allocazione della memoria.");
		return;
	}
	p1[0] = '\0';

	p2 = (char*)malloc(sizeof(char)*p2_len + 1);
	if ( !p2 )
	{
		printf("Errore nell'allocazione della memoria.");
		return;
	}
	p2[0] = '\0';

	if ( !LeggiStringa(szNomeFile1, p1, p1_len) )
		return;

	if ( !LeggiStringa(szNomeFile2, p2, p2_len) )
		return;

	if ( PREFIX_SIZE < p2_len )
		MaxPrefix = PREFIX_SIZE;
	else
		MaxPrefix = p2_len;

	if ( p1_len < PREFIX_SIZE )
	{
		pRisultato->len = len;
		pRisultato->pos1 = pos1x;
		pRisultato->pos2 = pos2x;
		strcpy(pRisultato->p1, strTemp1);
		strcpy(pRisultato->p2, strTemp2);

		free(p1);
		free(p2);

		return;
	}
	
	for ( x = MaxPrefix; x > 0; x--)
	{
		pTree = NULL;
		pos1 = 0;
		while ( pos1 < p1_len - x )
		{
			memcpy(strSearch, p1 + pos1, x);
			*(strSearch + x) = '\0';

			pTree = TreeInsertNode(pTree, strSearch, pos1);

			pos1++;
		}

		pos1 = 0;
		pos2 = 0;
		strTemp1[0] = '\0';
		strTemp2[0] = '\0';
		strSearch[0] = '\0';
		pLista = NULL;
		pNode = NULL;
		len = 0;
		len_prec = 0;
		numErrors = 0;
		bTrovato = 0;

		while ( pos2 < p2_len - x )
		{
			memcpy(strSearch, p2 + pos2, x);
			*(strSearch + x) = '\0';

			TreeSearch(pTree, &pNode, strSearch);
			if ( pNode != NULL )
			{
				pLista = pNode->pLista;

				while ( pLista != NULL )
				{
					pos1 = pLista->pos;
					numErrors = 0;
					k = x;
					post2 = pos2;
					if ( pos2 > x && pos1 > x )
					{
						k = 0;
						while ( (*(p2 + pos2) == *(p1 + pos1)) || (numErrors < 2) )
						{
							if ( *(p2 + pos2) != *(p1 + pos1) )
								numErrors++;
							pos1--;
							pos2--;
							if ( pos2 < 0 || pos1 < 0 )
								break;
						}
						pos1 += 1;
						pos2 += 1;
						numErrors = 0;
					}
					while ( (*(p2 + pos2 + k) == *(p1 + pos1 + k)) || (numErrors < 2) )
					{
						if ( *(p2 + pos2 + k) != *(p1 + pos1 + k) )
							numErrors++;
						k++;
					}
					if ( k > len_prec )
					{
						len = k;
						pos1x = pos1;
						pos2x = pos2;
						len_prec = len;

						bTrovato = 1;
					}
					pos2 = post2;
					pLista = pLista->next;
				}
			}

			pos2++;
		}
		TreeFree(pTree);
		if ( bTrovato )
			break;
	}

	pos1 = pos1x;
	pos2 = pos2x;
	len_prec = len;
	numErrors = 0;
	while ( (*(p1 + pos1) == *(p2 + pos2)) || (numErrors < 2) )
	{
		if ( *(p2 + pos2) != *(p1 + pos1) )
			numErrors++;
		pos2++;
		pos1++;
		if ( numErrors == 2 )
			break;
	}
	len = 0;
	numErrors = 0;
	while ( (*(p1 + pos1 + len) == *(p2 + pos2 + len)) || (numErrors < 2) )
	{
		if ( *(p2 + pos2 + len) != *(p1 + pos1 + len) )
			numErrors++;
		len++;
	}
	if ( len_prec < len )
	{
		pos1x = pos1;
		pos2x = pos2;
	}
	else
	{
		len = len_prec;
	}

	memcpy(strTemp1, p1 + pos1x, len);
	*(strTemp1 + len) = '\0';

	memcpy(strTemp2, p2 + pos2x, len);
	*(strTemp2 + len) = '\0';

	sprintf(strRes,
			"\nStringhe\n\n%s\n%s\n\ndi lunghezza %d trovate alle posizioni %d e %d\n",
			strTemp1,
			strTemp2,
			len,
			pos1x,
			pos2x);

	pRisultato->len = len;
	pRisultato->pos1 = pos1x;
	pRisultato->pos2 = pos2x;
	strcpy(pRisultato->p1, strTemp1);
	strcpy(pRisultato->p2, strTemp2);

	x = len_prec + 1;

	pos1 = 0;
	pos2 = pos2x + 1;
	strTemp1[0] = '\0';
	strSearch[0] = '\0';
	len_prec = len;
	len = 0;
	numErrors = 0;

	memcpy(strSearch, p2 + pos2, x);
	*(strSearch + x) = '\0';

	k = 0;
	while ( *(p1 + k) != *(p2 + k) )
		k++;
	pos1 = k;

	while ( pos1 < p1_len - x )
	{	
		memcpy(strTemp1, p1 + pos1, x);
		*(strTemp1 + x) = '\0';

		k = 0;
		while ( k < x )
		{
			if ( *(strSearch + k) != *(strTemp1 + k) )
				numErrors++;
			if ( numErrors > 2 )
				break;
			k++;
		}
		if ( k >= x && len_prec > len )
		{
			len = k;
			pos1x = pos1;
			pos2x = pos2;
			len_prec = len;

			memcpy(strTemp1, p1 + pos1x, len);
			*(strTemp1 + len) = '\0';

			memcpy(strTemp2, p2 + pos2x, len);
			*(strTemp2 + len) = '\0';

			sprintf(strRes,
					"\nStringhe\n\n%s\n%s\n\ndi lunghezza %d trovate alle posizioni %d e %d\n",
					strTemp1,
					strTemp2,
					len,
					pos1x,
					pos2x);

			pRisultato->len = len;
			pRisultato->pos1 = pos1x;
			pRisultato->pos2 = pos2x;
			strcpy(pRisultato->p1, strTemp1);
			strcpy(pRisultato->p2, strTemp2);

			break;
		}

		pos1++;
	}

	free(p1);
	free(p2);
}

/*
gcc -Wall -Wextra -pedantic -O2 Contest04BParz.c -o c04
*/

int main()
{
	Risultato ris;
	char strTempo[512];
	char strRes[1024];
	
	clock_t c_start, c_end;
	
	c_start = clock();

	Trova(FILE1, FILE2, &ris);
	
	c_end = clock();

	sprintf(strRes,
			"\nStringhe\n\n%s\n%s\n\ndi lunghezza %d trovate alle posizioni %d e %d\n",
			ris.p1,
			ris.p2,
			ris.len,
			ris.pos1,
			ris.pos2);

	printf(strRes);

	sprintf(strTempo, "\nTempo impiegato -> %5.5f secondi\n", (double)(c_end - c_start) / CLOCKS_PER_SEC);

	printf(strTempo);

	return 0;
}
Output:

Codice: Seleziona tutto

[vincenzo]$ gcc -Wall -Wextra -pedantic -O2 Contest04BParz.c -o c04
[vincenzo]$ ./c04

Stringhe

ACTGTCCTGAAGATCGCTTGGCATCTCCG
ACTGTCCTGCAGATCGCTTTGCATCTCCG

di lunghezza 29 trovate alle posizioni 50002 e 70002

Tempo impiegato -> 0.07040 secondi
In pratica leggiamo due file, DNA1.txt(100058 caratteri) e DNA2.txt(80058 caratteri) contenenti, ciascuno, una lunga sequenza di DNA.
Il programma trova la più lunga sottostringa comune che differisce, al più, per due caratteri.

Qui puoi scaricare i due file per la prova:

http://wikisend.com/download/618392/DNA.tar.gz
Grazie mille, vedrò cosa riuscirò a fare :(
PC: Asus F555UJ-DM059T CPU: Intel Core i7-6500U OS: Linux Mint KDE 18.3 RAM: 8GB GPU: nVidia GeForce-920M
Scrivi risposta

Ritorna a “Programmazione”

Chi c’è in linea

Visualizzano questa sezione: 0 utenti iscritti e 11 ospiti