Pagini recente » Cod sursa (job #1076537) | Cod sursa (job #2158182) | Cod sursa (job #793850) | Cod sursa (job #1758667) | Cod sursa (job #2870903)
#include<fstream>
#include<cstring>
using namespace std;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
char s1[4000002], s2[2000001];
int pi[2000001], rez[1001];
void kmp()
{
pi[0] = 0;
int len = strlen(s1);
for(int i=1; i<len; i++)
{
int j = pi[i-1];
if(j>0 && s1[j] != s1[i])
j = pi[j-1];
if(s1[i] == s1[j])
j++;
pi[i] = j;
}
}
int main()
{
cin.getline(s1, 2000001);
cin.getline(s2, 2000001);
strcat(s1, "#");
int len1 = strlen(s1);
strcat(s1, s2);
int len2 = strlen(s1);
kmp();
int ct = 0;
for(int i=len1; i<len2; i++)
{
if(pi[i] == len1-1 && ct<1000)
rez[++ct] = i-len1-2;
}
cout<<ct<<'\n';
for(int i=1; i<=ct; i++)
cout<<rez[i]<<" ";
return 0;
}