Pagini recente » Cod sursa (job #1334743) | Cod sursa (job #2897779) | Cod sursa (job #1029554) | Profil Harabula (rEbyTer) Adrian | Cod sursa (job #132979)
Cod sursa(job #132979)
#include <iostream>
#include <fstream>
#include <cstring>
#include <algorithm>
using namespace std;
int const MAXN = 500;
static char A [1+MAXN];
static char B [1+MAXN];
static int maxSuffix[1+MAXN][1+MAXN];
static int maxLen;
class SubString {
public:
void init (int pos) { position = pos; }
bool operator < (SubString const & co) {
return 0 > strncmp(&A[position], &A[co.position], maxLen);
}
bool operator == (SubString const & co) {
return 0 == strncmp(&A[position], &A[co.position], maxLen);
}
private:
int position;
};
SubString V[MAXN*MAXN+2];
static int lenV;
int main () {
ifstream sin("subsir.in");
sin >> A;
sin >> B;
int lenA = strlen(A), lenB = strlen(B), i, j;
maxSuffix[0][0] = 0; maxLen = 0;
for(i=1; i <= lenA; i ++) {
for(j=1; j <= lenB; j ++) {
if( A[-1+i] == B[-1+j] ) {
maxSuffix[i][j] = 1 + maxSuffix[-1+i][-1+j];
if(maxLen < maxSuffix[i][j]) {
maxLen = maxSuffix[i][j];
}
} else {
maxSuffix[i][j] = 0;
}
}
}
ofstream sout ("subsir.out");
if(0 == maxLen) {
sout << 0 << endl;
} else {
for(i = 1;i <= lenA; i ++) {
for(j = 1; j <= lenB; j ++) {
if(maxLen == maxSuffix[i][j]) {
V[lenV] . init (i-maxLen);
++ lenV;
}
}
}
make_heap(&V[0], &V[lenV]);
sort_heap(&V[0], &V[lenV]);
int count = 1;
for(i=1;i<lenV; i++) {
if(!(V[i] == V[-1+i])) {
++ count;
}
}
sout << count << endl;
}
return 0;
}