Pagini recente » Cod sursa (job #3342289) | Cod sursa (job #3327675) | Cod sursa (job #473576) | Cod sursa (job #2195801) | Cod sursa (job #3334859)
#include <bits/stdc++.h>
#define LMAX 2000000
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
int z[LMAX+1]; ///z[i] = lungimea maxima a prefixului sirului s care este si prefix al sufixului care incepe pe pozitia i
void z(string& s) ///algoritmul z
{
z[0]=s.size();
int l=0, r=0; ///capetele l si r ale z-box-ului
for(int i=1; i<s.size(); i++)
{
if(i>r) ///daca i este mai mare ca r, comparam fiecare caracter in mod brut
{
l=i;
r=i;
while(r<s.size() && s[r-l]==s[r]) r++; ///cat timp caracterele sunt identice
r--;
z[i]=r-l+1;
}
else
{
///daca suntem in interiorul z-box-ului
int j=i-l; ///pozitia din prefix asociata lui i
}
}
}
int main()
{
string a, b;
in >> a >> b;
string s=a+'$'+b;
z(s);
return 0;
}