Pagini recente » Cod sursa (job #2754013) | Cod sursa (job #336975) | Cod sursa (job #1934452) | Cod sursa (job #136373) | Cod sursa (job #1647349)
#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
#define MAX 2000010
char a[MAX], b[MAX];
int pi[MAX];
vector <int> v;
void fi(char c[], int n, int pi[])
{
int k;
pi[1] = 0;
for(int i = 2 ; i <= n ; i++)
{
k = pi[i - 1];
while(k && c[i] != c[k + 1])
k = pi[k];
if(c[i] == c[k + 1])
{
k++;
}
pi[i] = k;
}
}
int main()
{
int n, m, i, dr = 0, j;
fin >> a + 1;
fin >> b + 1;
n = strlen(a + 1);
m = strlen(b + 1);
fi(a, n, pi);
j = 0;
for(i = 1 ; i <= m ; i++)
{
while(j && a[j + 1] != b[i])
j = pi[j];
if(a[j + 1] == b[i])
j++;
if(j == n)
{
++dr;
if(dr <= 1000)
v.push_back(i - n);
}
}
fout << dr << "\n";
for(j = 0 ; j < v.size() ; j++)
fout << v[j] << " ";
}