#include <bits/stdc++.h>
using namespace std;
string lcs( string a, string b )
{
if( a.empty() || b.empty() ) return 0 ;
string current_lcs = "";
for(int i=0; i< a.length(); i++) {
size_t fpos = b.find(a[i], 0);
while(fpos != string::npos) {
string tmp_lcs = "";
tmp_lcs += a[i];
for (int x = fpos+1; x < b.length(); x++) {
tmp_lcs+=b[x];
size_t spos = a.find(tmp_lcs, 0);
if (spos == string::npos) {
break;
} else {
if (tmp_lcs.length() > current_lcs.length()) {
current_lcs = tmp_lcs;
}
}
}
fpos = b.find(a[i], fpos+1);
}
}
return current_lcs;
}
int main(){
freopen("antivirus_input_2.txt", "r", stdin);
freopen("output_antivirus2.txt", "w", stdout);
int T;
cin>>T;
for (int t = 1; t <= T; t++) {
vector <string> Arr(4);
vector <int> N(4);
string soluzione;
int M, valore;
for(int i=0; i<4; i++){
cin>>N[i];
}
cin>>M;
for(int i=0; i<4; i++){
cin>>Arr[i];
}
soluzione=lcs(*min_element(Arr.begin(), Arr.end()), *max_element(Arr.begin(), Arr.end()));
for(int i=0; i<4; i++){
valore=Arr[i].find(soluzione, 0);
if(valore==string::npos){
soluzione=lcs(*min_element(Arr.begin(), Arr.end()), Arr[i]);
}
}
cout<<"Case #"<<t<<": "<<Arr[0].find(soluzione, 0)<<" "<<Arr[1].find(soluzione, 0)<<" "<<Arr[2].find(soluzione, 0)<<" "<<Arr[3].find(soluzione, 0)<<endl;
}
return 0;
}
Buonasera, potreste darmi un consiglio su come migliorare questo codice?? Compila e in alcuni casi risponde (6/12) mentre invece ad altri mi da errato. Controllando l’output del codice sembra essere tutto regolare eccetto il fatto che escono alcuni numeri con più di 9 cifre.
Ciao, se ho compreso bene calcola la massima sequenza comune tra le quattro stringhe: a mio parere questa è la causa del bug. Il ragionamento, di base, è corretto, però ti sei dimenticato un’importante dettaglio specificato nel testo del problema.
Piccolo suggerimento: non stai usando la variabile M…
Spero di essermi spiegato bene, ma se qualcosa non ti è chiaro o ti serve qualche altro chiarimento chiedi pure! 
Ciao fabrizio, grazie per avermi risposto. Il codice di per sé funziona per lo meno nelle stringhe più piccole senza molti caratteri quindi il problema in questo caso non penso sia M, e nel momento in cui la stringa comune non viene trovata all’interno di una delle stringhe date in input allora mando alla funzione quella determinata stringa e quella più piccola. Per questo ho messo quell’if prima dell’output credendo di trovare una soluzione al bug ma non fa differenza 
. In quale modo mi consigli di utilizzare M??
Ho provato a inviare il problema con il tuo codice, ecco l’errore che mi viene dato:
In effetti, riguardando il codice con più attenzione, talvolta non viene selezionata la massima sottosequenza comune. Il tuo codice fallisce con questo input, per esempio:
1
6 8 7 10
2
ddpqpd
dpdqbppb
dpddpdd
dzpppddqqb
Alla fine del programma, lcs risulta essere dd, ma la soluzione è evidentemente pd. Per quanto la tua possa sembrare valida come soluzione, ne esiste una – anche con una complessità maggiore – che confronti tutte le stringhe in parallelo?
Suggerimento per l’implementazione: nested for-loop – cicli ogni volta su tutte le stringhe, ogni volta confrontando la sottosequenza ottenuta.
Per rispondere alla domanda a cosa serve M, ti rispondo con un’osservazione: cosa succede se la lunghezza di lcs è maggiore della lunghezza del virus?
Prova a riformulare il codice, è molto più semplice che sistemare la logica con lcs. Se hai ancora qualche dubbio sull’implementazione sono pronto a risponderti.
if (tmp_lcs.length()== M) {
current_lcs = tmp_lcs;
}
Ho cambiato questa condizione qui ma il problema risulta essere sempre lo stesso , anzichè fare cicli su cicli per verificare se la common substring è presente in tutte le stringhe, non è meglio farlo con un find sfruttando la libreria string?? Comunque hai ragione, il codice nel primo caso ritrova qq come sottostringa comune, ma com’è possibile se nell’altra stringa che mando alla funzione(in questo caso la più piccola sarebbe la prima) qq non c’è proprio ?? Scusami per le troppe domande ma vorrei capire a fondo il problema, hai molta pazienza 
.
Rispondo subito alla tua perplessità riguardo alla complessità del codice finale: considerato che i limiti delle variabili sono molto piccoli e il tempo di esecuzione conta relativamente (nelle territoriali si hanno vari minuti per eseguire il programma), è preferibile un codice meno ottimizzato ma più veloce da implementare, considerato che si hanno 3 ore per risolvere 4 problemi… Una soluzione con tempo \mathcal{O}(N_1N_2N_3N_4M) è comunque più che sufficiente per risolvere questo quesito!
Per il secondo punto, invece, va osservato cosa fa il programma (prendendo come esempio l’input che ho inviato nel mio messaggio precedente):
- Prima chiamata a
lcs: soluzione diventa “dd” (confrontando “ddpqpd” e “dzpppddqqb”)
- La prima stringa include “dd”
- La seconda stringa non include “dd”
- Seconda chiamata a
lcs: soluzione diventa “dp” (confrontando “ddpqpd” e “dpdqbppb”)
- La terza stringa include “dp”
- La quarta stringa non include “dp”
- Terza chiamata a
lcs: soluzione diventa “dd” (confrontando “ddpqpd” e “dzpppddqqb”)
- Cerca nelle quattro stringhe “dd”
Ora, come puoi vedere, il problema è che ogni volta che la soluzione viene sostituita tutte le stringhe precedenti non vengono aggiornate. Per ovviare a questo problema dovresti salvarti tutti i valori di soluzione non validi e poi aggiungere ulteriore logica.
Per questo, ti dicevo, la soluzione può essere molto più semplice – anche se magari risulta meno efficace.
Se ti può essere d’aiuto, ecco una base di partenza per la soluzione:
// Piccolo spunto: al posto di girarti tutti i for, esiste una condizione entro la quale non serve continuare a cercare il virus?
#include <iostream>
using namespace std;
void solve(int t)
{
int N1, N2, N3, N4;
cin >> N1 >> N2 >> N3 >> N4;
int M;
cin >> M;
string F1, F2, F3, F4;
cin >> F1 >> F2 >> F3 >> F4;
for (int i = 0; i < N1; i++) // itera su tutti i caratteri di N1
{
for (int j = 0; j < N2; j++) // itera su tutti i caratteri di N2
{
for (int k = 0; k < N3; k++) // itera su tutti i caratteri di N3
{
for (int l = 0; l < N4; l++) // itera su tutti i caratteri di N4
{
if (true) // quando deve stampare il risultato?
{
cout << "Case #" << t << ": " << i << ' ' << j << ' ' << k << ' ' << l << '\n';
return;
}
}
}
}
}
}
Buona fortuna con l’implementazione!
1 Mi Piace
Grazie mille, molto chiaro e soprattutto gentilissimo.
1 Mi Piace
for (int i = 0; i <= N1 - M; i++) {
string sub = F1.substr(i, M);
if (F2.find(sub) != string::npos && F3.find(sub) != string::npos && F4.find(sub) != string::npos) {
cout << "Case #" <<t<<": "<<i<<" "<<F2.find(sub)<<" "<<F3.find(sub)<<" "<<F4.find(sub)<<endl;
break;
}
}
Ciao @fabriziogiacomi ho trovato una soluzione ancora più corta di quella precedente estraendo dalla prima stringa F1, M caratteri a partire da i e poi controllo se è presente nelle altre stringhe. Chiaramente è molto più elaborata e non penso sia una soluzione spontanea ad una terry o qualsiasi altra gara.
È una soluzione alternativa, molto più simile a come l’ho implementata io nel mio invio. Ovviamente per ogni problema si può trovare una soluzione più ottimizzata, per cui io ti stavo solo suggerendo una delle tante strade per risolvere il problema.
Sono contento che tu abbia risolto, buona fortuna per i prossimi problemi!
1 Mi Piace
