[C] Confrontare due stringhe quasi identiche
-
- 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
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
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
PC: Asus F555UJ-DM059T CPU: Intel Core i7-6500U OS: Linux Mint KDE 18.3 RAM: 8GB GPU: nVidia GeForce-920M
- M_A_W_ 1968
- 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
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.
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?"
"...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?"
-
- 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
Qualcosa mi dice che non passerò l'esame di domani 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
PC: Asus F555UJ-DM059T CPU: Intel Core i7-6500U OS: Linux Mint KDE 18.3 RAM: 8GB GPU: nVidia GeForce-920M
- vaeVictis
- 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
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"
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.»
«I fear not the man who has practiced 10000 kicks once,
but I fear the man who has practiced one kick 10000 times.»
- Vincenzo1968
- 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
Potresti adattare questo codice che ho sviluppato una volta per partecipare a un contest:
Output:
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
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;
}
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
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)
-
- 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
Purtroppo l'algoritmo deve soddisfare la traccia che viene assegnata all'esame...Quell'algoritmo fa parte di un tema d'esame passato.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"
Grazie mille, vedrò cosa riuscirò a fareVincenzo1968 [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:
Output: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; }
In pratica leggiamo due file, DNA1.txt(100058 caratteri) e DNA2.txt(80058 caratteri) contenenti, ciascuno, una lunga sequenza di DNA.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
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
PC: Asus F555UJ-DM059T CPU: Intel Core i7-6500U OS: Linux Mint KDE 18.3 RAM: 8GB GPU: nVidia GeForce-920M
Chi c’è in linea
Visualizzano questa sezione: 0 utenti iscritti e 11 ospiti