Pagini recente » Cod sursa (job #2372675) | Cod sursa (job #1676604) | Cod sursa (job #2436997) | Cod sursa (job #1511573) | Cod sursa (job #1182695)
#include <stdio.h>
#include <limits.h>
#include <iostream>
#include <fstream>
#include <string>
#include <forward_list>
#include <queue>
using namespace std;
#define MAXN 2000001
#define IN "strmatch.in"
#define OUT "strmatch.out"
#define LARGE_INT_PRIME 1999999973
int m, n;
string word, text;
int wordHash;
int matchesFound, matchesTextIndex[MAXN], wordLength, textLength;
void read_input()
{
ifstream fin(IN);
getline(fin, word);
getline(fin, text);
fin.close();
wordLength = word.length();
textLength = text.length();
}
void computeWordHash()
{
for (int i = 0; i < wordLength; ++i)
{
wordHash += word[i];
}
}
void checkForEquality(int ti)
{
bool areMatch = true;
for (int i = 0; i < wordLength; ++i)
{
if (word[i] != text[i + ti])
{
areMatch = false;
break;
}
}
if (areMatch)
{
matchesTextIndex[matchesFound++] = ti;
}
}
void resolve()
{
computeWordHash();
int curHash = 0;
for (int i = 0; i < wordLength; ++i)
{
curHash += text[i];
}
if (curHash == wordHash)
{
checkForEquality(0);
}
for (int i = wordLength; i < textLength; ++i)
{
curHash = curHash + text[i] - text[i - wordLength];
if (curHash == wordHash)
{
checkForEquality(i - wordLength + 1);
}
}
}
void print_solution()
{
ofstream fout(OUT);
fout << matchesFound << '\n';
for (int i = 0; i < matchesFound; ++i)
{
fout << matchesTextIndex[i] << ' ';
}
fout.close();
}
int main()
{
read_input();
resolve();
print_solution();
//char x;
//cin >> x;
return 0;
}