Pagini recente » Cod sursa (job #1228523) | Cod sursa (job #2609180) | Cod sursa (job #2518578) | Cod sursa (job #1603008) | Cod sursa (job #2173688)
#include <iostream>
#include <fstream>
#include <string.h>
#include <vector>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
#define N_MAX 2000005
char P[N_MAX], T[N_MAX];
int n, m, Pi[N_MAX], k, rez;
vector <int> v;
int main()
{
f >> P + 1;
f >> T + 1;
n = strlen(P + 1);
m = strlen(T + 1);
for(int i = 2; i <= n; i++)
{
while(k > 0 && P[k + 1] != P[i])
k = Pi[k];
if(P[k + 1] == P[i]) k++;
Pi[i] = k;
}
for(int i = 1; i <= m; i++)
{
while(k > 0 && P[k+1] != T[i])
k = Pi[k];
if(P[k + 1] == T[i]) k++;
if(k == n)
{
rez++;
if(rez <= 1000)
v.push_back(i - n);
k = Pi[k];
}
}
g << rez << "\n";
for(int i = 0; i < v.size(); i++)
g << v[i] << " ";
return 0;
}