Pagini recente » Cod sursa (job #1276240) | Cod sursa (job #2420092) | Cod sursa (job #394824) | Cod sursa (job #860893) | Cod sursa (job #3203848)
#include <fstream>
#include <cstring>
#include <vector>
const int NMAX=2000005;
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
void pi(char *s);
char s[2*NMAX], t[NMAX];
int pii[2*NMAX], lg, i;
vector <int> ans;
int main()
{
fin>>s;
lg=strlen(s);
for(i=lg; i>=1; i--) s[i]=s[i-1];
fin>>t;
strcat(s, "#");
strcat(s, t);
pi(s);
fout<<ans.size()<<'\n';
for(auto i:ans) fout<<i<<' ';
return 0;
}
void pi(char *s)
{
int i, poz;
pii[1]=0;
for(i=2; s[i]; i++)
{
poz=i-1;
while(true)
{
if(s[pii[poz]+1]==s[i])
{
pii[i]=pii[poz]+1;
break;
}
else if(poz==0)
{
pii[i]=(s[i]==s[1]);
break;
}
else poz=pii[poz];
}
if(pii[i]==lg && ans.size()<1000) ans.push_back(i-2*lg-1);
}
}