Pagini recente » Istoria paginii runda/cerculdeinfo-lectia15-ev_p_s_q_dq_dp | Cod sursa (job #1874412) | Monitorul de evaluare | Cod sursa (job #385939) | Cod sursa (job #2742784)
#include <cstring>
#include <fstream>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
#define NumarElementeFiecareSir 2000004
char a[NumarElementeFiecareSir];///primul sir
char b[NumarElementeFiecareSir];///al doilea-->cel in care cautam sirul a
int v[NumarElementeFiecareSir];
int ElementeAfisare[1006];
int Length_first,Length_second;
int NumarElementeAfisat=1;
int min(int a, int b){
if(a<b) return a;
return b;
}
void read(char k[]){
f>>k;
}
void solve()
{
v[1]=0;
int prefixVal=0,i;
for(i=2;i<=Length_first;i++)
{
while(prefixVal>0 && a[prefixVal+1]!=a[i])
prefixVal=v[prefixVal];
if(a[prefixVal+1]==a[i])
prefixVal++;
v[i]=prefixVal;
}
prefixVal=0;
for(i=1;i<=Length_second;i++)
{
while(prefixVal>0 && a[prefixVal+1]!=b[i])
prefixVal=v[prefixVal];
if(a[prefixVal+1]==b[i])
prefixVal++;
if(prefixVal==Length_first)
{
if(NumarElementeAfisat<1000)
ElementeAfisare[NumarElementeAfisat++]=i-prefixVal;
else
NumarElementeAfisat++;
}
}
}
int main()
{
read(a);
read(b);
Length_first=strlen(a);
Length_second=strlen(b);
int i;
for(i=Length_first;i>=1;--i)
a[i]=a[i-1];
for(i=Length_second;i>=1;--i)
b[i]=b[i-1];
solve();
NumarElementeAfisat--;
g<<NumarElementeAfisat<<"\n";
for(i=1;i<=min(NumarElementeAfisat, 1001);i++)
g<<ElementeAfisare[i]<<" ";
return 0;
}