Cod sursa(job #1346857)

Utilizator AlphaZoneRAlbert Ferencz AlphaZoneR Data 18 februarie 2015 17:34:07
Problema Subsir Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.13 kb
#include <fstream>
#include <string>
#include <iostream>
using namespace std;

	short t[502][502];

	void kiir(int sa, int sb){


		for (int i = 1; i <= sa ; ++i)
		{
			for (int j = 1; j <= sb ; ++j)
			{
				cout << t[i][j] << " ";
			}
			cout << endl;
		}

	}

	int main(int argc, char const *argv[])
	{
		ifstream in("subsir.in");
		ofstream out("subsir.out");
		
		string a;
		string b;
		in >> a >> b;

		int sa = a.size();
		int sb = b.size();
		for (int i = 1; i <= sa ; ++i)
		{
			for (int j = 1; j <= sb ; ++j)
			{
				if (a[i - 1] == b[j - 1]) {
					t[i][j] = t[i - 1][j - 1] + 1;
				} else {
					t[i][j] = max(t[i-1][j],t[i][j-1]);
				}
			}
		}

		int max = 0;
		for (int i = 1; i <= sa ; ++i)
		{
			for (int j = 1; j <= sb ; ++j)
			{
				if(t[i][j] > max){
					max = t[i][j];
				}
			}
		}

		int db = 0;
		for (int i = 1; i <= sa ; ++i)
		{
			for (int j = 1; j <= sb ; ++j)
			{
				if (t[i][j] == 1 and t[i - 1][j] == 0 and t[i][j - 1] == 0 and t[i + 1][j] == 1 and t[i][j + 1] == 1){
 					++db;
				}
			}
		}

		out << db << endl;
		// kiir(sa,sb);
	}