Pagini recente » Cod sursa (job #1084415) | Cod sursa (job #807521) | Cod sursa (job #789182) | Cod sursa (job #385070) | Cod sursa (job #3124260)
#include <bits/stdc++.h>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
const int N = 4000010;
char s[N];
int n,m,Z[N],R,L,P,cnt;
vector<int> poz;
int main()
{
string A;
f>>A;
m=A.size();
strcpy(s,A.c_str());
s[m]='$';
f>>A;
strcat(s,A.c_str());
n=strlen(s);
for(int i=1; i<n; i++)
{
/// calculam functia z[] pentru toate pozitiile
/// cazul 1-suntem in afara box-ului
/// refacem complet box-ul incepand din L=i ( brut )
if(i>R)
{
L=R=i;
P=0;
while(s[P]==s[R])
{
P++;
R++;
}
Z[i]=P;
R--;
}
/// Pozitia i este in interiorul box-ului [L,R]
else
{
int k=i-L; /// k = pozitia in box a lui i ( pozitia din prefix care
/// corespunde lui i in box)
/// cazul 2-suntem in interiorul boxului dar la o pozitie
/// din care prefixul se opreste strict inainte de terminarea box-ului
/// k nu bate in afara prefixului corespunzator box-ului
/// deci si i va bate in box exact la fel de mult ca di k in prefix>
if(i+Z[k]-1<R)
Z[i]=Z[k];
/// ALTFEL
/// cazul 3-sun in interiorul box-ului si din pozitia i pana la capatul
/// box-ului am un prefix de s[] - aici trebuie sa verificam daca
/// creem un box nou care incepe in i si se termina CEL PUTIN in R
/// Resetam L in i avem deja asigurat ok pana la R
/// dar e posibil sa putem extinde box-ul si dupa i
/// adica este posibil sa avansam capatul R al box-ului
else
{
L=i;
R++;
P=R-L;
while(s[P]==s[R])
{
P++;
R++;
}
R--;
Z[i]=P;
}
}
if(Z[i]==m)
{
cnt++;
if(cnt<1000)
poz.push_back(i-m-1);
}
}
g<<cnt<<'\n';
for(auto it:poz)
g<<it<<' ';
g<<'\n';
return 0;
}
//
// L 0 P
// P L R
//asdfasasdx .... asdfasasdf????
// P k [ i
// | 0 k
// V
// 0
//
// din i ma pot extinde cel mult pana la pozitia R
// dar Z[k] imi spune ca din i ma pot extinde pana la i+Z[k]-1, dar numai daca
// i+Z[k]-1 < R
// Ce se intampla daca i+Z[k]-1>=R. Atunci
//
//
// k=i-L
// >>>>> >>>>>
// bbbbbbbbbbbibbbbbbbbbbbbbb
//
// /
// /
// /
// /
// /
//ppppppppkppppppppppppppppp
//>>>>> >>>>>
//
//
//