Pagini recente » Cod sursa (job #452928) | Cod sursa (job #2786913) | Cod sursa (job #2334820) | Cod sursa (job #2665749) | Cod sursa (job #3147831)
#include <fstream>
#include <cstring>
using namespace std;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
char sir1[2000005], sir2[2000005];
int v[2000005];
int cnt;
int poz[2000005];
int main()
{
cin >> sir1 >> sir2;
int i = 1, j = 0;
int lg = strlen(sir1);
while(i < lg)
{
while(sir1[i] != sir1[j] && j != 0)
j = v[j-1];
if(sir1[i] == sir1[j])
{
v[i] = v[i-1] + 1;
i++;
j++;
}
else
{
v[i] = 0;
i++;
}
}
int k = 1;
i = 1;
int lg2 = strlen(sir2);
while(k < lg2-1)
{
while(sir1[i] == sir2[k] && i < lg-1)
{
i++;
k++;
}
if(i == lg-1 && sir1[i] == sir2[k])
{
cnt++;
poz[cnt] = k - i;
i = v[i-1];
}
while(sir1[i] != sir2[k] && i > 0)
i = v[i-1];
if(i == 0 && sir1[i] != sir2[k])
k++;
}
cout << cnt << '\n';
if(cnt > 1000)
cnt = 1000;
for(int i = 1; i <= cnt; i++)
cout << poz[i]<<' ';
return 0;
}