Pagini recente » Cod sursa (job #1129556) | Cod sursa (job #1320096) | Cod sursa (job #3142179) | Cod sursa (job #2941994) | Cod sursa (job #2483588)
#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>
#define Nmax 2000005
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char a[Nmax], b[Nmax];
int n, m, total;
int pr[Nmax]; // lungimea celui mai lung sufix care e si prefix
vector <int> sol;
void build(char a[], int n)
{
int j=0;
for (int i = 2; i <= n; i++)
{
while (j!=0 && a[i]!=a[j+1]) j=pr[j];
if (a[i] == a[j+1]) j++;
pr[i]=j;
}
}
int main()
{
f >> (a+1) >> (b+1);
n=strlen(a+1), m=strlen(b+1);
build(a, n);
int j = 0;
for (int i = 1; i <= m; i++)
{
while (j!=0 && b[i]!=a[j+1]) j=pr[j];
if (a[j+1] == b[i]) j++;
if (j == n)
{
total++;
if (sol.size()<1000) sol.push_back(i-n);
}
}
g << total << '\n';
for (auto i:sol) g << i << " ";
return 0;
}