Pagini recente » Cod sursa (job #1992924) | Cod sursa (job #1616833) | Cod sursa (job #1655635) | Cod sursa (job #1628561) | Cod sursa (job #1892803)
#include <iostream>
#include <cstring>
using namespace std;
const int Q=2000008;
char v[Q],s[Q];
int d[Q],rez[Q];
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
gets(v+1);
//cin>>v+1;
int size_v=strlen(v+1);
for(int i=2; i<=size_v; i++)
{
int l=d[i-1];
while(l && v[i]!=v[l+1])
l=d[l];
if(v[i]==v[l+1])
l++;
d[i]=l;
}
/*
d[i] este lungimea maxima a doua
subsecvente identice, una care incepe
la pozitia 1 din v si alta
care se termina la pozitia i din v
*/
//continuare
gets(s+1);
//cin>>s+1;
int size_s=strlen(s+1);
int t=0;
int contor=0;
for(int p=1; p<=size_s; p++)
{
while(t && v[t+1]!=s[p])
t=d[t];
if(v[t+1]==s[p])
t++;
if(t==size_v)
{
contor++;
if(contor<=1000)
rez[contor]=p-size_v;
t=d[t];
}
}
cout<<contor<<"\n";
for(int i=1; i<=contor; i++)
cout<<rez[i]<<" ";
}