Pagini recente » Rating Burlacu Theodor-Andrei (theodor.burlacu) | Cod sursa (job #1003444) | Cod sursa (job #505258) | Cod sursa (job #1040501) | Cod sursa (job #841600)
Cod sursa(job #841600)
//Vasilut
//Z-Algorithm
#include<fstream>
#include<string>
#include<vector>
#define NN 2000005
using namespace std;
ofstream out("strmatch.out");
string a,b,s;
int n;
vector<int>sol;
int z[ 2*NN ];
void read();
void Z_A();
void write_sol();
int main()
{
read();
Z_A();
write_sol();
return 0;
}
void read()
{
ifstream in("strmatch.in");
in >> a >> b;
s = a + '?' + b;
n = s.size();
}
void Z_A()
{
//z[i] - cel mai lung substring care incepe din s[i] si este prefix al lui S
int st,dr ,i ;
st = dr = 0;
for ( i =1 ; i<n; i++)
{
if ( i > dr ) // nu exista nici un prefix al lui S care sa inceapa inainte de i si sa se termine in sau dupa i
{
st = i;
dr = i;
while ( dr < n && s[ dr - st ] == s[ dr ] )
dr++;
z[i] = dr - st;
dr -- ;
}
else
{
int k = i - st;
if ( z[k] < dr - i + 1 )
z[i] = z[k];
else
{
st = i;
while ( dr < n && s[ dr - st ] == s[ dr ] )
dr++;
z[i] = dr - st;
dr -- ;
}
}
if ( z[i] == a.size() )
{
int val = i - z[i];
--val;
sol.push_back(val);
}
//sol.push_back( i - z[i] - 1 );
//out << i - z[i] - 1 <<" ";
}
}
void write_sol()
{
out << sol.size() <<'\n';
int how = 0;
for(int i=0;i<sol.size() && how < 1000; ++i )
{
++how;
out << sol[i] <<" ";
}
}