Pagini recente » Cod sursa (job #2828116) | Cod sursa (job #862377) | Cod sursa (job #2035290) | Cod sursa (job #1461969) | Cod sursa (job #2496452)
#include <fstream>
#include <cstring>
using namespace std;
ifstream cin ("strmatch.in");
ofstream cout ("strmatch.out");
char a[2000005], b[2000005];
int c[2000005], v[1005];
int n, m;
void prefix()
{
int j = 0;
for(int i = 2; i <= n; i++)
{
while(j != 0 && a[i] != a[j + 1])
j = c[j];
if (a[i] == a[j + 1])
j++;
c[i] = j;
}
}
int j = 0, cnt = 0;
int main()
{
cin.getline(a + 1, 2000005);
cin.getline(b + 1, 2000005);
n = strlen(a + 1);
m = strlen(b + 1);
prefix();
for(int i = 1; i <= m; i++)
{
while(j != 0 && b[i] != a[j + 1])
j = c[j];
if(b[i]==a[j + 1])
{
j++;
if(j == n)
{
if (cnt <= 1000)
v[cnt] = i - n;
cnt++;
}
}
}
cout << cnt << "\n";
for(int i = 0; i < cnt && i < 1000; i++)
cout << v[i] <<" ";
return 0;
}