Pagini recente » Cod sursa (job #983702) | Cod sursa (job #212497) | Cod sursa (job #829750) | Cod sursa (job #1561992) | Cod sursa (job #2910626)
#include <cstdio>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <stack>
#include <map>
#include <cstring>
#include <climits>
#include <unordered_map>
#define NMAX 2000003
#define DIM 1001
//Solutia cu KMP
//Compexitate O(n+m)
using namespace std;
FILE* fin, * fout;
char str1[NMAX], str2[NMAX];//cele 2 stringuri in care vrem sa cautam caracterele comune
int prefix[NMAX];//vectorul de prefixe(aici am pastrat indici)
int sol[DIM],nr;
int len1, len2;
int main() {
fin = fopen("strmatch.in", "r");
fout = fopen("strmatch.out", "w");
fscanf(fin, "%s\n", str1+1);
fscanf(fin, "%s", str2+1);
len1 = strlen(str1+1);
len2 = strlen(str2+1);
int lung = 0;//lungimea celui mai mare prefix care poate fi creat dinamic din primul string
prefix[1] = 0;
for (int i = 2; i <= len1; i++)
{
while (lung != 0 && str1[i] != str1[lung + 1])
{
//ma duc la indicele primului prefix
lung = prefix[lung];
}
if (str1[i] == str1[lung + 1])
{
lung++;//cresc lungimea prefixului maxim care poate fi format
}
prefix[i] = lung;
}
//acum imi testez vectorul de prefixe pe stringul 2(unde vreau sa caut)
lung = 0;//incep cu lungimea de la 0
for (int i = 1; i <= len2; i++) {
while (lung != 0 && str2[i] != str1[lung + 1]) {
lung = prefix[lung];//ma duc la prefixul initial
}
if (str2[i] == str1[lung + 1])
{
lung++;//cresc lungimea pentru ca am gasit un prefix de lungime mai mare
}
if (lung == len1)
{
//am un prefix de lungimea primului string
nr++;
if (nr < DIM)
{
sol[nr] = i - len1;
}
lung = prefix[lung];//mai micsorez lungimea pentru ca vrem sa cautam si potrivirea urmatoare
}
}
fprintf(fout, "%d\n", nr);
for (int i = 1; i <= min(DIM, nr); i++)
{
fprintf(fout, "%d ", sol[i]);
}
return 0;
}