Cod sursa(job #132979)

Utilizator mgntMarius B mgnt Data 7 februarie 2008 00:21:41
Problema Subsir Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.57 kb
#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;
}