Pagini recente » Cod sursa (job #2411205) | Cod sursa (job #3237801) | Cod sursa (job #2604210) | Cod sursa (job #3275515) | Cod sursa (job #3000530)
#include <fstream>
#include <cstring>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
int n , m , l , v[200005] , p[200005] , q , cnt , k;
char a[200005] , b[200005];
int main()
{
f >> ( a + 1) >> ( b + 1 );
n = strlen(a + 1);
m = strlen(b + 1);
p[1] = 0;
q = 0;
for ( int i = 2 ; i <= n ; i++)
{
while(q > 0 && a[q + 1] != a[i]);
{
q = p[q];
}
if(a[q + 1] == a[i])
{
q++;
}
p[i] = q;
}
q = 0;
for (int i = 1 ; i <= m ; i++)
{
while(q > 0 && a[q + 1] != b[i])
{
q = p[q];
}
if(a[q + 1] == b[i])
{
q++;
}
if(q == n)
{
cnt++;
if(cnt <= 1000)
{
k++;
v[k] = i - n;
}
}
}
g << cnt << '\n';
for ( int i = 1 ; i <= k ; i++)
{
g << v[i] << " ";
}
return 0;
}