Pagini recente » Istoria paginii runda/concurs_2 | Cod sursa (job #3150210) | Atasamentele paginii runda_de_verificare1 | Statisticile problemei Echilibrare | Cod sursa (job #1769740)
#include <iostream>
#include <fstream>
#include <cstdlib>
#include <vector>
#include <algorithm>
#include <limits>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
#define nr_char 256
int** computeTransFun(string &P)
{
int m = P.size();
int** delta = new int*[m+1];
for(int i = 0 ; i <= m ; i++)
delta[i] = new int[nr_char]{};
int i, lps = 0, x;
// Fill entries in first row
for (x = 0; x < nr_char; x++)
delta[0][x] = 0;
delta[0][P[0]] = 1;
// Fill entries in other rows
for (i = 1; i<= m; i++)
{
// Copy values from row at index lps
for (x = 0; x < nr_char; x++)
delta[i][x] = delta[lps][x];
// Update the entry corresponding to this character
delta[i][P[i]] = i + 1;
// Update lps for next row to be filled
if (i < m)
lps = delta[lps][P[i]];
}
return delta;
}
bool PksuffixPqa(const string & P,int k,int q,int a)//O(m)
{
if(k == -1)
return true;
if(P[k]!=a) //
return false;
for(int i = k-1 ; i >= 0 ; i--,q--)
if(P[i]!=P[q])
return false;
return true;
}
int** precomputeDeltaFunction(const string& P)//O(m^3*|sigma|) functia de tranzitie naiva
{
bool ok;
int m = P.size(),k;
int** delta = new int*[m+1];
for(int i = 0 ; i <= m ; i++)
delta[i] = new int[nr_char]{};
for(int q = 0 ; q <= m ; q++)//O(m)
for(int a = 0 ; a < nr_char; a++)//O(m*|sigma|)
{
k = min(m+1,q+2);
do
{
k--;
ok = PksuffixPqa(P,k-1,q-1,a);//O(m^3*|sigma|)
}
while(!ok);//O(m^2 *|sigma|)
delta[q][a] = k;
}
return delta;
}
void finiteStateAutomaton(const string& T,int** delta,int m,vector<int>& pos)//O(n+ functieTranzitie)
{
int n = T.size();
if(m>n)
return;
int q = 0;
for(int i = 0 ; i < n ; i++)
{
q = delta[q][(int)T[i]];
if(q == m)
pos.push_back(i-m+1);
}
}
int main()
{
vector<int> pos;
string s,w;
in >> w >> s;
finiteStateAutomaton(s,computeTransFun(w),w.size(),pos);
out<<pos.size()<<'\n';
for(int j = 0 ; j < std::min((int)pos.size(),1000); j++)
out<<pos[j]<<" ";
return 0;
}