Pagini recente » Cod sursa (job #2311738) | Cod sursa (job #2777863) | Cod sursa (job #3148551) | Cod sursa (job #2590610) | Cod sursa (job #2554467)
#include <fstream>
#include <cstring>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
char ch1[2000001];
char ch2[2000001];
char s[4000002];
int pi[4000002];
int ans[4000002];
int main()
{
in.get(ch1+1,2000001);
int l1=strlen(ch1+1);
in.get();
in.get(ch2+1,2000001);
int l2=strlen(ch2+1);
int n=l1+l2;
int i;
for(i=1;i<=n+1;i++)
{
if(i<=l1)
s[i]=ch1[i];
else if(i==l1+1)
s[i]='#';
else
s[i]=ch2[i-l1-1];
}
pi[1]=0;
for(i=2;i<=n+1;i++)
{
int now=pi[i-1];
while(now>0 && s[now+1]!=s[i])
{
now=pi[now];
}
if(s[now+1]==s[i])
{
now++;
}
pi[i]=now;
}
int cnt=0,maxim=0;
for(i=1;i<=n+1;i++)
{
if(pi[i]>maxim)
maxim=pi[i],cnt=0;
if(pi[i]==maxim)
{
if(cnt<1000)
ans[++cnt]=i-l1-l1-1;
else
continue;
}
}
out<<cnt<<'\n';
for(i=1;i<=cnt;i++)
{
out<<ans[i]<<" ";
}
return 0;
}