Pagini recente » Cod sursa (job #967236) | Cod sursa (job #1039457) | Cod sursa (job #1027515) | Cod sursa (job #862752) | Cod sursa (job #1468955)
#include <cstdlib>
#include <iostream>
#include <vector>
#include <cmath>
#include <fstream>
using namespace std;
const char iname[] = "strmatch.in";
const char oname[] = "strmatch.out";
bool suffix(const string &P, int k,const int &i, const char &c)
{
string S;
S.assign(P,0,i);
S+=c;
k--;
for(int j = S.length() - 1 ; k >= 0 && j>=0; k--, j--)
{
if(P[k]!= S[j])
return false;
}
return true;
}
int Match(const string &T, int it, const vector<vector<int> > &delta)
{
int x = T.length();
int y = delta.size();
for(int q = 0; it < x; ++it)
{
int r = ((T[it] - 'a' < 0) ? T[it] - 'A' + 26 : T[it] - 'a');
if(r < 0) r = 52;
// cout << T[it] << ' ' << r << '\n';
q = delta[q][r];
if(q == y) return it;
}
return -1;
}
void Create_delta(const string &P, const string &Sigma, vector<vector<int> > &delta)
{
int p = P.length();
for(int i = 0; i < p; i++)
{
int s = Sigma.length();
vector<int> dummy;
delta.push_back(dummy);
for(int j = 0; j < s; j++)
{
int k = min(p+1, i+2);
do
{
k--;
}while(!suffix(P,k,i,Sigma[j]));
(delta[i]).push_back(k);
}
}
}
int main()
{
int a[1005],p,t;
a[0] = 0;
ifstream in(iname);
ofstream out(oname);
vector< vector<int> > delta;
string P = "ABA", T = "CABBCABABABA";
string Sigma = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";
in >> P >> T;
p = P.length();
t = T.length();
Create_delta(P,Sigma,delta);
int q = 0;
do{
if(q == 0)
q = Match(T, 0,delta);
else
q = Match(T, q-p+2, delta);
if(q > 0)
{
++a[0];
if(a[0] < 1005)
a[a[0]] = q - p + 1;
}
}while(q >= 0 && q < t);
out << a[0] << '\n';
for(int i = 1; i <= a[0] && i < 1002; i++)
out << a[i] << ' ';
return 0;
}