Pagini recente » Cod sursa (job #297264) | Cod sursa (job #2509602) | Cod sursa (job #3279627) | Cod sursa (job #1353793) | Cod sursa (job #2350388)
#include "pch.h"
#include <iostream>
#include <fstream>
#include< cstring>
#define minim(a, b) ((a < b) ? a : b)
#define max 200
using namespace std;
char s1[max], s2[max];
int pi[max ];
int n, m;
void citire()
{
ifstream in("strmatch.in");
in.getline(s1, max);
in.getline(s2, max);
n = strlen(s1);
m = strlen(s2);
for (int i = n; i > 0; i--)
s1[i] = s1[i - 1];
for (int j = m; j > 0; j--)
s2[j] = s2[j - 1];
}
void make_prefix()
{
int q = 0;
int i;
//cout << s1 << endl;
for (i = 2, pi[1] = 0; i <= n; i++)
{
while (q && s1[q + 1] != s1[i])
q = pi[q];
if (s1[q + 1] == s1[i])
q++;
pi[i] = q;
}
}
int main()
{
citire();
//cout << s2 << endl;
make_prefix();
int contor = 0;
int pozitions[max];
int q = 0;
for (int i = 1; i <= m; i++)
{
while (q && s1[q + 1] != s2[i])
q = pi[q];
if (s1[q + 1] == s2[i])
q++;
if (q == n)
{
if(contor<=1000)
pozitions[++contor] = i - n;
}
}
ofstream out("strmatch.out");
out << contor<< endl;
for (int i = 1; i <= contor; i++)
out << pozitions[i] << " ";
return 0;
}